text:
# Derivative of an expoential within an exponential

1. Nov 4, 2007

### sprint

[SOLVED] derivative of an expoential within an exponential

help. i need help on finding the derivative of an exponential within an exponential

1. The problem statement, all variables and given/known data

d/dx of e^(e^4x)

2. Relevant equations

d/dx of e^(e^4x)

3. The attempt at a solution

d/dx of e^(e^4x)

i don't know how to attempt this cause the function im interested is in the power of e

2. Nov 4, 2007

### hotcommodity

We know that the derivative of an exponential is simply the exponential times the derivative of power term, right?

$$\frac{d}{du} e^u = e^uu'$$

You're going to have to apply the chain rule.

Does that help?

3. Nov 4, 2007

### sprint

i think we are not looking at the same problem. my problem is an exponential within an exponential

d/dx e^(e^4x)

4. Nov 4, 2007

### hotcommodity

It's not the exact equation that you need to apply, but that's where you start. If I let $$u = e^{4x}$$, then I must first find the derivative of $$e^u$$.

I know $$\frac{d}{du} e^u = e^uu'$$.

So you know what "u" is, now you must find the derivative of "u" and plug it into the above equation.

5. Nov 4, 2007

### sprint

oooooh.

i see. i guess just use substitution letting u = e^(4x)

by any chance, is the correct answer 4e^(4x) times e^(4x) = 4e^(8x)

?

6. Nov 4, 2007

### hotcommodity

Not quite, you want to think of "u" as separate from everything else and only plug it in at the end. If $$u = e^{4x}$$, what's the derivative, u' ?

7. Nov 4, 2007

### sprint

thats exactly what i did. i made "u" separate.

and the derivative of u is 4e^(4x), to answer your question.

8. Nov 4, 2007

### hotcommodity

Right, so you'd have $$4e^{e^{4x}}e^{4x}$$. I didn't see you type in the $$e^{e^{4x}}$$ part.

9. Nov 5, 2007

### sprint

wow. totally confusing.

but i think the answer is what i stated earlier...

4e^(4x) times e^(4x)

i get this by sticking to the basics and using the chain rule and substitution

Last edited: Nov 5, 2007
10. Nov 5, 2007

### hotcommodity

I'm not trying to confuse you, haha, but I'd hope that you walk away from this understanding what's going on. Let's say I wanted to find the derivative of $$e^{e^x}$$. I'd use the chain rule once again letting $$u = e^x$$. So I'd have:

$$\frac{d}{du} e^u = e^uu'$$

Find u':

$$u' = e^x * 1$$

And plug u and u' into the first equation to get the derivative:

$$e^{e^x}*e^x*1$$

Right?

11. Nov 5, 2007

### sprint

check it. i was wrong. the answer should be

4e^(4x) times e^(e^(4x))

which is

u' times e^u

via the chainrule

12. Nov 5, 2007

### sprint

i follow you. you are right.

13. Nov 5, 2007

### sprint

and how do you type in the equations like that? it looks clean...

14. Nov 5, 2007

### hotcommodity

Haha, you just use the "tex" tags. You can click on the equation itself to see how you would type it in. I think there's a tutorial somewhere here on the site.

15. Nov 5, 2007

### sprint

ok. thanks. lol.

16. Nov 5, 2007

### hotcommodity

You're quite welcome :)


text:
• Free Veritas GMAT Class
Experience Lesson 1 Live Free

Available with Beat the GMAT members only code

• Get 300+ Practice Questions

Available with Beat the GMAT members only code

• Award-winning private GMAT tutoring
Register now and save up to $200 Available with Beat the GMAT members only code • Free Practice Test & Review How would you score if you took the GMAT Available with Beat the GMAT members only code • 1 Hour Free BEAT THE GMAT EXCLUSIVE Available with Beat the GMAT members only code • Free Trial & Practice Exam BEAT THE GMAT EXCLUSIVE Available with Beat the GMAT members only code • Magoosh Study with Magoosh GMAT prep Available with Beat the GMAT members only code • 5 Day FREE Trial Study Smarter, Not Harder Available with Beat the GMAT members only code • 5-Day Free Trial 5-day free, full-access trial TTP Quant Available with Beat the GMAT members only code ## GMAT VS GRE This topic has 3 expert replies and 13 member replies Goto page • 1, • 2 Surfinjosh Newbie | Next Rank: 10 Posts Joined 08 Oct 2008 Posted: 3 messages #### GMAT VS GRE Wed Oct 15, 2008 6:00 pm I have the option between the GMAT and GRE and I need a minimum of 500 or 1000 respectively. WHich one would you rather take if you had the option??? Thank you for the help. _________________ Josh Need free GMAT or MBA advice from an expert? Register for Beat The GMAT now and post your question in these forums! EricKryk Senior | Next Rank: 100 Posts Joined 31 Mar 2009 Posted: 83 messages Upvotes: 3 Sat Apr 18, 2009 7:33 pm How is accepting GRE rather than GMAT equivalent to lowering standards? That's like saying that schools that accept the ACT along with the SAT are of lower standard. I disagree. Such schools may feel like both tests are adequate at predicting which applicants are likely to handle the workload well. VP_Jim GMAT Instructor Joined 01 May 2008 Posted: 1223 messages Followed by: 13 members Upvotes: 185 Mon Mar 30, 2009 8:54 am I know that a lot of top PhD programs, especially, take either the GRE or GMAT. For example, the University of Chicago GSB PhD program in finance actually prefers the GRE to the GMAT. http://www.chicagogsb.edu/phd/admissions.aspx So, I certainly wouldn't base my decision about how good a school is on whether it takes the GRE! _________________ Jim S. | GMAT Instructor | Veritas Prep OGMATTERS Senior | Next Rank: 100 Posts Joined 21 Jun 2009 Posted: 43 messages Upvotes: 1 Target GMAT Score: 0 Fri Nov 13, 2009 8:07 pm USCGTO wrote: do what you want to. GRE and GMAT both feed different individual applications. Wow. I hope u're atleast 10 yr old before you posted this, and thought a moment before just licking up the keyboard. Do some research before you try to put someone down. Harvard/Stanford both accept the GRE http://www.gsb.stanford.edu/MBA/admission/test_scores.html http://www.hbs.edu/news/releases/greandgmat.html Northwestern accepts the GMAT for its law program. http://www.law.northwestern.edu/academics/ajd/admissions.html ### GMAT/MBA Expert beatthegmat Site Admin Joined 13 Feb 2006 Posted: 6707 messages Followed by: 964 members Upvotes: 1249 Mon Nov 02, 2009 10:54 am There was a really interesting article we published about this several weeks ago. Check it out: http://www.beatthegmat.com/a/2009/09/30/the-gmat-or-the-gre _________________ Sorin Istrate - Community Manager MBA Watch - Your one-stop shop for all MBA program research ### GMAT/MBA Expert Dan@VinciaPrep Master | Next Rank: 500 Posts Joined 01 Nov 2009 Posted: 384 messages Followed by: 12 members Upvotes: 92 Sun Nov 01, 2009 9:57 am Surfinjosh wrote: I have the option between the GMAT and GRE and I need a minimum of 500 or 1000 respectively. WHich one would you rather take if you had the option??? Thank you for the help. General 1) If you know which schools you want to apply to first see which test(s) they accept 2) G.R.E. is less expensive ($140 in the US and $180 in Europe) than the GMAT ($250)

3) Many people do worse on the GMAT math when they first take a practice test because most people have never encountered a data sufficiency problem which takes some getting used to.
Verbal

The GRE uses questions that require a much larger vocabulary than the GMAT.

The GMAT has a grammar section that the GRE doesn't have. In this section you are given a sentence and asked to correct it.

The GMAT has logic questions that are not on the GRE. In general this sections tests your ability in argument constrution, argument evaluation, and formulating and evaluating a plan of action.

Conclusion- if youâ€™re really good at vocabulary or learning vocabulary, or if youâ€™re not very good with American English Grammar you should consider taking the GRE. Otherwise, the GMAT might be more for you.

I got this info from http://fr.standardizedtests.org/content/gmat-vs-gre which gives updated information on this from time to time.

Last edited by Dan@VinciaPrep on Tue Nov 17, 2009 1:19 am; edited 1 time in total

aim-wsc Legendary Member
Joined
20 Apr 2006
Posted:
2470 messages
Followed by:
14 members
85
Target GMAT Score:
801-
Wed Sep 30, 2009 7:25 pm
& we have new article published this week about the same topic!
Check it out: I totally agree with the author http://www.beatthegmat.com/a/2009/09/30/the-gmat-or-the-gre

_________________
Getting started @BTG?

Please do not PM me, (not active anymore) contact Eric.

ken3233 Master | Next Rank: 500 Posts
Joined
31 Dec 2008
Posted:
125 messages
2
Mon Mar 30, 2009 8:18 am
valbos wrote:
If a grad school accepts a gre instead of gmat I prob would not go there, that is like lowering standards.
The testing service is arguing that the two tests are comparable in difficulty, and in their capacity to measure aptitude. I think some pretty competitive schools are accepting the GRE now. If you do a google search on the subject, you can find lots of interesting information on the subject.

valbos Newbie | Next Rank: 10 Posts
Joined
27 Mar 2009
Posted:
3 messages
Sun Mar 29, 2009 9:07 pm
If a grad school accepts a gre instead of gmat I prob would not go there, that is like lowering standards.

ken3233 Master | Next Rank: 500 Posts
Joined
31 Dec 2008
Posted:
125 messages
2
Sat Mar 28, 2009 2:49 am
USCGTO wrote:
do what you want to.

GRE and GMAT both feed different individual applications. Wow. I hope u're atleast 10 yr old before you posted this, and thought a moment before just licking up the keyboard.
You may not be aware that recently many MBA programs announced they would accept the GRE in lieu of the GMAT.

Thanked by: OGMATTERS
ken3233 Master | Next Rank: 500 Posts
Joined
31 Dec 2008
Posted:
125 messages
2
Sat Mar 28, 2009 2:44 am
Based on my experience, I would say that the GRE is easier than the GMAT. The distinction is especially true of the quantitative section; I found GRE math to be much less difficult than GMAT math.

I have not taken the GMAT yet, but I did take the GRE several years ago. I obtained scores of 800 verbal and 760 quantitative.

Last month, before I began preparing seriously for the GMAT, I took the computerized practice tests available on the official GRE and GMAT websites just to test my skills. I found the results to be very interesting.

On the two GRE practice tests, I obtained:

1) 750 verbal; 750 quantitative
2) 710 verbal; 760 quantitative

That same weekend, I took the two GMATPrep practice tests, obtaining scores of:

1) 640 (40 verbal; 36 quantitative)
2) 660 (41 verbal; 39 quantiative)

The difference in scores between my GRE and GMAT practice runs have convinced me that the GMAT is a tougher test than the GRE.

valbos Newbie | Next Rank: 10 Posts
Joined
27 Mar 2009
Posted:
3 messages
Fri Mar 27, 2009 10:33 pm
u people r not going to get an 800 u should b more worried about the job u wont have once u earn the stellar degree

USCGTO Newbie | Next Rank: 10 Posts
Joined
04 Jan 2009
Posted:
3 messages
Target GMAT Score:
800
Sun Jan 04, 2009 7:25 am
do what you want to.

GRE and GMAT both feed different individual applications. Wow. I hope u're atleast 10 yr old before you posted this, and thought a moment before just licking up the keyboard.

aim-wsc Legendary Member
Joined
20 Apr 2006
Posted:
2470 messages
Followed by:
14 members
85
Target GMAT Score:
801-
Wed Oct 15, 2008 7:11 pm
Personally, I would take GMAT, because its of "my type"

But I think the exam (registration) fees of GRE is cheaper than GMAT.

_________________
Getting started @BTG?

Please do not PM me, (not active anymore) contact Eric.

VP_Jim GMAT Instructor
Joined
01 May 2008
Posted:
1223 messages
Followed by:
13 members
185
Wed Oct 15, 2008 7:02 pm
I much prefer the GMAT. I'm not sure if the GRE has changed at all, but back when I took it, the exam had a lot of vocabulary questions (mostly analogies, if I recall) in the verbal section. I was always taught to use the most simple word that fits the situation, so I did not learn a lot of those ridiculous long and arcane words that no one actually uses.

On the other hand, I don't think the GRE has data sufficiency, so if you're really uncomfortable with those but your vocabulary is awesome, maybe you'd want to do the GRE. Take a practice test for each and see how they feel. Here's a link to a free practice test from Veritas that I find pretty accurate:

http://www.veritasprep.com/gmat-preparation/free-practice-GMAT

Good luck!

_________________
Jim S. | GMAT Instructor | Veritas Prep

Thanked by: 7712019
Goto page
• 1,
• 2

### Best Conversation Starters

1 Roland2rule 174 topics
2 lheiannie07 110 topics
3 ardz24 64 topics
4 LUANDATO 56 topics
5 swerve 46 topics
See More Top Beat The GMAT Members...

### Most Active Experts

1 Brent@GMATPrepNow

GMAT Prep Now Teacher

150 posts
2 Jeff@TargetTestPrep

Target Test Prep

145 posts
3 Rich.C@EMPOWERgma...

EMPOWERgmat

116 posts
4 GMATGuruNY

The Princeton Review Teacher

103 posts
5 Scott@TargetTestPrep

Target Test Prep

98 posts
See More Top Beat The GMAT Experts

format: plain


text:
# Python: Generate SHA3 hashes for files with custom rate and capacity values

I am working on a project which requires comparing the performance of SHA3 on different values of rate and capacity. I have implemented the same in Python and my program works fine, however, the performance of my program is slow in comparison to the standard SHA3 implementation.

The standard implementation of SHA3-512 (using hashlib.sha3_512()) takes ~0.016 seconds for hashing a 1.5 MB file whereas my implementation of SHA3-512 for the same file takes ~20 seconds. I want the performance of my code to be similar to the standard implementation done using hashlib.sha3_512().

I am unable to figure out a way to optimise my code. My implementation is as follows:

import binascii
import time
class Keccak:

__STATE_LENGTH = 1600
__DELIMITED_SUFFIX = 0x06
__SHA3_RATE_LENGTH = 256
def __init__(self,variant=2):
self.__state_bytes_length = self.__STATE_LENGTH // 8
self.__delimited_suffix = self.__DELIMITED_SUFFIX

self.__SHA3_RATE_LENGTH = variant
self.__rate_bytes_length = self.__SHA3_RATE_LENGTH // 8
self.__state_in_bytes = bytearray([0 for i in range(self.__state_bytes_length)])
self.__capacity_bytes_length = self.__state_bytes_length - self.__rate_bytes_length
self.__hash_bytes_length = self.__capacity_bytes_length//2
self.__hash_bytes = bytearray()

@staticmethod
def __rotate_word(word, n):
return ((word >> (64 - (n % 64))) + (word << (n % 64))) % (1 << 64)

@staticmethod
return sum((byte_array[i] << (8 * i)) for i in range(8))

@staticmethod
def __store_64_bytes(integer):
return list((integer >> (8 * i)) % 256 for i in range(8))

def __run_inner_hash_functions(self, lanes):
R = 1
for round in range(24):

# θ
C = [lanes[x][0] ^ lanes[x][1] ^ lanes[x][2] ^ lanes[x][3] ^ lanes[x][4] for x in range(5)]
D = [C[(x + 4) % 5] ^ self.__rotate_word(C[(x + 1) % 5], 1) for x in range(5)]
lanes = [[lanes[x][y] ^ D[x] for y in range(5)] for x in range(5)]

# ρ and π
(x, y) = (1, 0)
current = lanes[x][y]
for t in range(24):
(x, y) = (y, (2 * x + 3 * y) % 5)
(current, lanes[x][y]) = (lanes[x][y], self.__rotate_word(current, (t + 1) * (t + 2) // 2))

# χ
for y in range(5):
T = [lanes[x][y] for x in range(5)]
for x in range(5):
lanes[x][y] = T[x] ^ ((~T[(x + 1) % 5]) & T[(x + 2) % 5])

# ι
for j in range(7):
R = ((R << 1) ^ ((R >> 7) * 0x71)) % 256
if R & 2:
lanes[0][0] = lanes[0][0] ^ (1 << ((1 << j) - 1))

return lanes

def __run_hash_function(self):
# In column first order
lanes = [[self.__load_64_bytes(self.__state_in_bytes[8 * (x + 5 * y):
8 * (x + 5 * y) + 8])
for y in range(5)]
for x in range(5)]

lanes = self.__run_inner_hash_functions(lanes)

state_in_bytes = bytearray(200)
for x in range(5):
for y in range(5):
state_in_bytes[8 * (x + 5 * y):
8 * (x + 5 * y) + 8] = self.__store_64_bytes(lanes[x][y])

self.__state_in_bytes = state_in_bytes

def get_hash_of(self, input_bytes):
block_size = 0
message_offset = 0

# === Absorb all the input blocks ===
while message_offset < len(input_bytes):
block_size = min(len(input_bytes) - message_offset, self.__rate_bytes_length)

for i in range(block_size):
self.__state_in_bytes[i] ^= input_bytes[message_offset + i]

message_offset += block_size

if block_size == self.__rate_bytes_length:
self.__run_hash_function()
block_size = 0

# === Do the padding and switch to the squeezing phase ===
self.__state_in_bytes[block_size] ^= self.__delimited_suffix

if ((self.__delimited_suffix & 0x80) != 0) and (block_size == (self.__rate_bytes_length - 1)):
self.__run_hash_function()

self.__state_in_bytes[self.__rate_bytes_length - 1] ^= 0x80
self.__run_hash_function()

# === Squeeze out all the output blocks ===
while self.__hash_bytes_length > 0:
block_size = min(self.__hash_bytes_length, self.__rate_bytes_length)
self.__hash_bytes += self.__state_in_bytes[0: block_size]
self.__hash_bytes_length -= block_size

if self.__hash_bytes_length > 0:
self.__run_hash_function()

return binascii.hexlify(self.__hash_bytes)

variant = int(input("Enter the rate value of SHA3: \n"))
keccak = None
try:
keccak = Keccak(variant)
except ValueError as v:
print(v)
exit(0)

file_name = input("Enter a file name: ")
file = open(file_name, "rb")
# for i in range(10):
start = time.time()
original_hash = keccak.get_hash_of(contents)
end = time.time()
execution_time = end-start
#execution_times.append(execution_time)
print("Hash:" + str(original_hash)[2:-1] + "\nLength of Hash: " + str(len(original_hash)))
print("Time taken for hashing: " + str(float(execution_time)) + " Seconds")
file.close()

UPDATE: Can anyone suggest what changes do I need to make if I want to run this same code with cython?

• python is slow no surprise there Jan 7 at 12:08
• The functions in hashlib are written in C to make use of possible hardware optimizations. So they are obviously much faster than your Python-interpreted implementation. Thus, you will not achieve your goal in making a pure Python implementation equally performant. Jan 7 at 14:02
• Is there any reason you can not use the hashlib library specifically made to do this? Jan 12 at 13:05
• @N3buchadnezzar I want to customise the size of rate and capacity and the hashlib library won't let me do that until I tweak the source code. :( 2 days ago

Let's start with some conventions. Class definitions typically have two leading whitespaces before them and two after. Uppercase variables generally means it's a global variable. Single letter variable names can occasionally be fine, but I'd only use it if it relates to a known mathematical formula, and I'd want that formula kept with the code somewhere; for some of your variables it would be better to just type out pi or whatever instead of renaming this to y and only mentioning that in a comment. Private variables (two leading underscore to name-mangle) is sometimes used but quite rarely. We generally use _ for toss-away temporary variables to signify as much (e.g. [0 for i in range(self.__state_bytes_length)] would be [0 for _ in range(self.__state_bytes_length)]).

You have quite the amount of magic numbers in your code, and you have a lot of bit manipulation that isn't well documented. I'd die a little inside if I had to review this code for work.

Doing a sys.exit(0) upon catching an exception is really strange - an exit code of 0 typically means success.

Instead of manually closing the file you've opened it would be better to use a context manager (with open(path, mode) as f:).

Also, if you want to do profiling with time prints, it would be better to use perf_counter, and even better yet to use a module like timeit or to use the profile module.

With that out of the way, let's move on to what you actually requested feedback on: the performance (as in timewise). I don't think you're ever going to get the time down to what hashlib's function does without using pypy or leaving python entirely - i.e. you'd need to extend with C or C++ or some other compiled/lower level language. There are some minor improvements that you can do (replace calling list with list comprehension, combine your nested loops using itertools), but python is just not built for these kind of speeds.

• file is a built-in? That's news to me.. Jan 7 at 16:22
• My bad - it was in python2 but has since been removed.


text:
# Home-baked graphics

A couple of commenters have asked what software package I use to create the graphs that appear in bit-player posts–illustrations like the one below, which is a slightly improved version of something I posted last week. Let’s call it Figure 1.

Prompted by these inquiries, I immodestly ask myself: Why do my graphs look so darn good? I immodestly answer: It’s not because of any packaged software! I don’t need a cake mix, or even a recipe. These are home-baked graphs, made from scratch out of locally grown organic pixels.

I have strong opinions about the aesthetics of scientific illustrations, and I could certainly spout off about the design elements of Figure 1, such as that putty-colored background, just dark enough to allow drop-out white grid lines, yet neutral enough to avoid competing with the data curves, which also have a distinctive color scheme on which I could discourse at length. Yes, I can talk the Tufte talk. But I think the commenters were really asking how I create the graphs rather than why they’re so elegant, and so I’m going to focus here on the practical programming problem.

Most of my experience in drawing pictures with a computer comes from the world of print publishing, where the final product is ink on paper rather than pixels on a screen. Compared with the online environment, print has some advantages, notably higher resolution (up to 1,000 dots per centimeter) and precise control over typography and color. But print also has obvious limitations: On a magazine page, there are no mouseovers or clickable buttons, and you can’t make a square knot twirl in 3D.

Thirty years ago, the big challenge for computer-generated illustrations was not how to draw the picture but how to get it out of the computer and onto the printing press. You couldn’t just export a PDF and place it in a Quark or InDesign document; none of those things existed. The only practical option was to print out the artwork, photograph it, and “strip” the negative into the page-size film that would be used to make the press plate. Because of this emphasis on printouts, most of the effort went into programming the printer rather than the computer.

The figure below is the first published computer-generated illustration I had a hand in creating. It appeared in Scientific American in 1983.

The array of 282 tiny bar graphs was produced with an Epson MX-80 dot-matrix printer, using escape codes to fire combinations of the eight pins in the printhead. Of course the MX-80 was a black-and-white device. The two-color illustration was created from two separate printouts. Also, the Epson letterforms were replaced with typeset characters.

The world of computer-generated illustrations changed dramatically with the arrival of PostScript, the “page description language” created by John Warnock and his colleagues at Adobe Systems (based in part on earlier work at Evans and Sutherland and Xerox PARC). PostScript was designed as a complete programming language rather than just a file format or a set of drawing commands. And something else set it apart as well: attention to details of graphic design. With most earlier software (such as programs based on the Apple Quickdraw library), trying to create publishable figures was an exercise in frustration. For example, the apparent weight of a line would vary depending on its orientation: lighter when vertical or horizontal, heavier when diagonal. PostScript allows very precise control over such niceties of presentation. To take another example, where lines meet the edge of a graph, you don’t want to have to choose between falling short and overshooting; PostScript provides the tools needed to make it look right.

(The version in the rightmost panel is created by allowing the colored lines to extend outside the background box, and then applying a clipping mask that cuts off all objects at the boundary of the box.)

Obsessing over minute details like these may seem comically fussy, but I believe that neatness counts in these matters. To some extent, illustration is an art of illusion. Graphs and diagrams work best when you can look through them rather than at them. The viewer should be seeing the underlying information or abstraction–the array of correlation coefficients, the function y = f(x), or whatever–rather than noticing the mechanics of how the drawing was constructed. A ragged edge is the kind of distraction that destroys the illusion.

Although PostScript was a giant step forward from the MX-80 command set, in the early years it was still just another printer language, not a computer language. The only way I could execute a PostScript program was to send it to a laser printer and wait to see what came out. Sometimes it was a long wait. I had no way of running a PostScript program on the computer itself. (Ghostscript came later.)

My first PostScript illustrations were created as hand-written PostScript programs; the same language was used both for doing the computations and for presenting the results. The faces at right were created in this way. (They were inspired by the work of Herman Chernoff and drawn to illustrate an American Scientist article by Robert Levine in 1990.) The dual role of the language caused me a moment of disorientation just now when I went looking for my records of this project. I found an EPS (encapsulated PostScript) file, which I knew was the finished illustration, but where was the source code? And then I remembered: It’s the same file! Open it up in Ghostscript or Adobe Illustrator and you see those silly faces smiling or scowling at you; open the same file in a text editor, and you see procedures for drawing elements of the faces:

   /draweyes
{ newpath
dx dy eyewidth eyeheight 0 360 ellipse stroke
ex ey eyewidth eyeheight 0 360 ellipse stroke
} bind def
/drawpupils
{ fx fy pupilsize pupilsize 0 360 ellipse fill
gx gy pupilsize pupilsize 0 360 ellipse fill
} bind def

Bill Casselman, the graphics editor of the Notices of the American Mathematical Society, still favors this direct-to-PostScript methodology. He has written an excellent guidebook, taking you from the basics of PostScript through an elaborate library for rendering three-dimensional objects.

But here I part company from Casselman; I’d rather not do all my computing in PostScript. It’s not that I have anything against the language itself, but the development environment is not to my taste. I therefore adopted the modus operandi of writing a program in my language of choice (usually some flavor of Lisp) and having that program write a PostScript program as its output. After doing this on an ad hoc basis a few times, it became clear that I should abstract out all the graphics-generating routines into a separate module. The result was a program I named lips (for Lisp-to-PostScript).

Most of what lips does is trivial syntactic translation, converting the parenthesized prefix notation of Lisp to the bracketless postfix of PostScript. Thus when I write (lineto x y) in Lisp, it comes out x y lineto in PostScript. The lips routines also take care of chores such as opening and closing files and writing the header and trailer lines required of a well-formed PostScript program.

But the lips interface is low-level, confined to drawing individual dots, line segments, rectangles and the like. Assembling a complete graph out of these primitives is tedious. For example, the grid of white lines in Figure 1 would have to be drawn one line at a time, with each line specified by a sequence of commands such as

    (newpath)
(moveto u v)
(lineto x y)
(stroke)

Before you can issue those commands, you have to calculate u, v, x and y. Clearly, a higher-level front end is needed; like everyone else, I call mine plot.

At the core of any plotting program is a simple operation: mapping points from an abstract user space to coordinates in a rectangular pane, the page space. In Figure 1, the y axis runs from 0 to 5000; values in this range have to be scaled to the dimensions of the graph, which is about 300 PostScript points, or 11 centimeters. Mathematically, the transformation is straightforward. Indeed, if I wished I could leave all the arithmetic to the PostScript interpreter, simply passing in the appropriate matrix elements for scaling and translation. This is an attractive option; it would allow plot to work entirely in user space. But a few niggling details get in the way. Consider the tick marks along the y axis in Figure 1. Their vertical positions are conveniently expressed in user coordinates: one tick every 500 units. But what about the length of the ticks–their horizontal extent? This dimension is purely concerned with the appearance of the graph and has nothing to do with the content; it ought to be expressed in unscaled units of points or pixels.

Here’s a possible solution: Let everything inside the rectangular frame of the graph–the area with the putty-colored background in Figure 1–go through the scaling engine, but define everything outside the frame, including the tick marks and the axis labels, directly in page coordinates. If you think this is the final answer, take a look at Figure 2:

In this nonsensical graph (constructed just for this occasion), data points are indicated by stars, crosses and diamonds. The positions of those glyphs ought to be defined in user space, but the drawing commands that create the shapes are properly defined in page coordinates. If we tried to draw the glyphs in user space, their size and shape would vary with position in the graph.

What’s the best way to deal with this messy situation? Is there some tidy solution that will reconcile the two coordinate systems and allow all dimensions to be treated uniformly? I don’t believe so; it’s just in the nature of graphs to mix up elements from these two disparate realms. We look through a window into a world of data or mathematical abstractions, but we also draw our own little doodles on the window itself.

Of course there are solutions; they’re just not as pretty as I would like. My own strategy for coping is to attach extra information to each geometric point, indicating whether or not the x and y coordinates are to go through the scaling transformation. This is less troublesome than it might seem; from the user’s point of view, it’s almost always invisible.

In writing the lips and plot programs, I walk a path that is already worn smooth by many earlier footsteps. I don’t know who wrote the first computer program for plotting data, but it probably came soon after the first program for producing data. Today we have hundreds of clever, comprehensive, well-designed and well-maintained programs for plotting and graphing. Gnuplot is very capable; Grace is one I’ve never used but I’ve heard good things about it; Mathematica, Sage, R, MATLAB, Octave and the like all have elaborate graphics facilities built in; the Python world, as usual, has an overabundance of options; there are a few libraries for my beloved Lisp; you can even do dataviz online.

All of which raises the question of why I bother to roll my own. I’ll never keep up–or even catch up–with the efforts of major software companies or the huge community of open-source developers. In my own program, if I want something new–treemaps? vector fields? the third dimension?–nobody is going to code it for me. And, conversely, anything useful I might come up with will never benefit anyone but me.

The trouble is, every time I try working with an external graphics package, I run into a terrible impedance mismatch that gives me a headache. Getting what I want out of other people’s code turns out to be more work than writing my own. No doubt this reveals a character flaw: Does not play well with others.

In any case, the time for change is coming. My way of working is woefully out of date and out of fashion. PostScript is a technology that even Adobe seems to regard as outmoded. And making ultraprecise PostScript graphs is quite silly when their destination is the web; before I can put them online, I have to convert them to low-res PNG images. Furthermore, a PostScript-based workflow loses out on all the interactive richness of the web. These are deathly still images. How can I expect to earn any web cred when my work is not even clickable, much less multitouch-enabled?

If I continue in my stubborn, do-it-yourself mode, I could replace the PostScript back end with one that generates SVG. This wouldn’t be a major undertaking. But is SVG the right answer? It’s been around for more than a decade and you still don’t see much of it in the wild. And there are horrid browser incompatibilities. I suspect that Javascript (and JQuery) has a brighter future. And if I can get over my abreaction to libraries, there are plenty of options. Advice anyone?

Ron Renaud’s graphs using Javascript in a canvas element are really very pretty, and they give me renewed hope that web graphics can measure up to a print standard. But is the world quite ready for the canvas? This is a blog, after all. Lots of people get to it with an RSS reader, not a web browser.

Zvika requests a link to a higher-resolution PNG. I don’t know how to do that. I can make a larger PNG, but the resolution–the dots per centimeter–is really determined by the screen you’re looking at. Which is not to say that larger illustrations wouldn’t be a good idea. When I redesign these pages, I want to allow more room for bigger pictures.

Gary Reuben suggests Python Matplotlib and the ggplot2 package for R. The latter is new to me, and very impressive. I want to go read more about it.

Several other readers favor SVG. I’m okay with that. It looks easy to change my current software to generate SVG output instead of (or in addition to) PostScript. The question remaining for me is whether SVG on the web is something that browsers (and, again, RSS readers) can swallow without choking.

John Haugland mentions PDF as the successor to PostScript. I couldn’t possibly survive without PDF these days, but I don’t see it as an ideal medium for illustrations embedded in web pages. Reading PDFs within a browser requires a plugin, which some people refuse to install. (I’m one of those people.) Furthermore, because PDF is a binary format based on a directory of offsets to tables, it’s more trouble to write PDF files than either PostScript of SVG.

Nate mentions Processing, the graphics and animation language created by Casey Reas and Ben Fry. I’ve written about this before at bit-player and elsewhere. I’m a big fan, but Processing is essentially a front end to Java, and I have reservations about embedding Java applets in web pages. John Ressig’s reimplementation of the language in Javascript overcomes that problem, and one of these days I’ll get around to doing something serious with it.

Finally, Marc asks for a look at my Lisp code. I’m always shy about sharing such unfinished things, but here it is.

Update 2010-03-28: When commenter Zvika asked for higher-resolution graphics, my reply was unhelpful; let me now try to say something more useful.

Even though I can’t do anything to improve screen resolution, I can, as Zvika notes, provide a larger version of each image. The Wikipedia way of doing this, which Zvika mentions, is to link to a separate HTML page, which replaces everything on the page you’re currently reading. As a test, I’ve done this with Figure 1 above; click on that figure and you’ll be whisked away to a supersized version of the graph. To get back here, you’ll have to use your browser’s “back” button.

Another approach, adopted by, for example, the New York Times, is a pop-up window. I’ve done this with Figure 2 above; click on it and a new window with a bigger version will open in front of this page.

Personally, I dislike both of these strategies. I want to see the words and the pictures at the same time in the same context. I suppose I could implement (or swipe) some glitzy Ajaxian solution that expands the artwork box within the window. But I still feel the right solution is to redesign the pages so that there’s room for larger illustrations in the first place. (Admittedly I’ve been meaning to do that for more than a year.)

There’s also a question about how best to make use of a more spacious picture box. In the supersized Figure 1, the transformation is much like an optical enlargement, projecting the same information at larger scale. The overall dimensions are doubled, and so is the width of each line, the size of the type, and so on. This is probably the answer for those troubled by visual deficiencies (including my own presbymyopic eyes).

In Figure 2 I have enlarged the illustration by 150 percent but kept all the individual graphic elements (line weights, labels, the glyphs that mark data points) the same size. This kind of rescaling allows information to be read from the graph with greater precision.

Perhaps a middle way is sensible here. Indeed, maybe type should scale as the square root of graph size?

This entry was posted in computing.

### 20 Responses to Home-baked graphics

1. Frank Meulenaar says:

I always use Mathematica, it exports to eps/SVG, renders to jpg/png (in the resolution you require) and probably anything else you would ever like.

Still there is some work to be done, like choosing the correct background color.

2. 0x69 says:

If i need to plot from Python - then I use MatplotLib package. Otherwise - I just make plots with OpenOffice Calc - still good for simple graphs :-)

3. Rob Renaud says:

I wrote my own Javascript/canvas code to render graphs. I think it would be worthwhile for you to do so as well. With the kind of attention to detail you have, writing “to the metal” with calls to canvas is the way to go rather than using a library.

I am particularly proud of the first graph on this page, for example.

http://rftgstats.com/

Things like custom icons, variance bars, and drawing meaningful contours are things you just won’t find in a high level library.

Before writing my own custom code, I used the flot javascript plotting library, which is pretty and quick, but not particularly customizable. Certainly, if I wanted a nice plot in 15 minutes rather than a gorgeous, domain tailored one in 3 hours, I’d use flot.

4. Zvika says:

As long as you’re making high-quality PostScript images for your blog, could you perhaps have the image link to a higher-resolution PNG which would open in a new window? That way, the OCD-afflicted perfectionists among your readers (myself included, of course) could appreciate your meticulous drawing capabilities, which are all but lost in a 400×400 pixel image.

5. Gary Ruben says:

I use and would recommend the Python Matplotlib library (which I thought you had used to produce your Figure 1 above until I read further). It lets you control clipping, line curves and bevelling etc. for vector plots, and uses a high quality antialiasing engine for raster plots. Admittedly you’re pretty much forced to use Python rather than Lisp, but I gather you’re resigned to using something different.

I also think the R ggplot2 package looks nice
which you could also drive from Python via the RPy2 interface if you were so inclined.

6. Oni says:

I think that SVG is the right choice. Not because the format is good per se, but because it can be converted into whatever you want and it’s quite easy to traverse it with any language (as long as there is a library that can navigate trough XML).

I’ve used it extensively for my thesis. I then used a script that passed all text to LaTeX in order to take care of the typesetting (while the original image, with stripped text, was converted in pdf and placed as background).

7. klwe says:

SVG works everywhere except crappIE browsers. If you don’t care about outdated tech, then there’s no problem.

8. Jos Hirth says:

I used SVG for some graphs. Here is some example:

http://kaioa.com/b/0803/cat_capacity.svgz

It’s fairly compact. If you take a look at the response header you can see that it’s only 3,422 bytes in size (thanks to gzip compression). It automatically adjusts to the size of the view-port and it works in any semi-recent (non-IE) browser.

One interesting detail is that the graphs contain the raw unaltered data. E.g. “L 8,1614.482″ means with an initial capacity of 8 characters it took 1614.482 msecs to run the benchmark.

Also, I made my benchmarks output the path data directly. It’s a very simple format. M = move to, L = line to, and X/Y pairs.

“M 0,2130.2948 L 8,1614.482 L , …”

I only had to copy that stuff and paste it over in Inkscape’s XML editor. At the end I flipped and scaled it by applying some matrix.

I mean… I could have generated some CSV and then open it in Calc or Excel, but that’s just too boring. ;)

9. In my opinion, the modern dialect of PostScript - PDF - is the way to go. It provides all of the graphics primitives needed to do the work right, and it’s very reliably viewed on a wide variety of platforms, as well as very readily brought to print in both POD and offset printing contexts, and most importantly, the de facto viewer is extremely reliable in terms of rendering what the file presents.

The real problem with SVG is that it’s hard to get clients to view it reliably. To that end, there are a lot of tools which convert from +css to PDF, and some of the better ones (my favorite is PrinceXML) can embed SVG, giving you the expressive notation of SVG with the reliable viewing target of PDF. Above and beyond that, it gives you the really quite nice pagination of CSS3 and the convenient framing of a full HTML+CSS3 implementation.

It isn’t free, but if you want to bail on PostScript, PDF is the place to go. It’s PostScript 2 - it loses the programming language, but it’s a direct descendant of the old post-compile format. Look at the specification some time.

10. hyperkinetic says:

Ahhh, the MX-80. Fine printer.

11. Marc says:

I’m currently learning Lisp. Any chance of getting a look at your code?

12. A long time ago I learned enough PostScript to be dangerous, and about four or five times a year I find some reason to actually code up a diagram or graph using PostScript. I find ghostscript to be very good at converting PostScript to raster formats, for the web as well. The ability of GhostScript to read TrueType and PostScript fonts means that you can do some fun things, like typesetting checkerboard positions:

A checkerboard position from my checkers program Milhouse

13. Nate says:

I wonder if the Processing language (processing.org) might be of interest to you. This is a language with many graphical conveniences that doesn’t sacrifice control. When I first saw your graphics I thought they were created with Processing–it may be worth a look.

14. crowther says:

All of this talk about SVG and so forth is beyond me, but I wanted to thank you for permitting yourself the immodesty of praising Fig. 1. Now that you’ve mentioned it, I can appreciate the putty-colored background and white grid lines and may try to imitate those in the future.

On an unrelated note, I gave “Group Theory in the Bedroom” to a relative (a chemistry professor who likes math puzzles and such) a couple of years ago and he really liked it. Now I need to get him another present. Do you have any recommendations based on his enjoyment of that book?

15. Zvika says:

What I meant was a larger image size (I guess resolution is an innacurate term). You could keep the images as is, but have them link to a larger image, so that when the user clicks on an image he will see a full-screen version. For example, this is more or less how images are handled in Wikipedia.

16. Making you WordPress theme wider in not that hard. It took me around a hour to find all the places. I even now have a post explaining how todo it.

http://simeonpilgrim.com/blog/2010/04/02/how-to-make-your-wordpress-theme-wider/

Nice graphs by the way.

17. Zach Beane says:

You might enjoy my Common Lisp library Vecto, which is designed to mimic the PDF drawing model but output directly to a PNG. I use it all the time for scratch programs that produce charts or plots. For more a more elaborate use, see http://xach.com/moviecharts/

18. Andre says:

“But I think the commenters were really asking how I create the graphs rather than why they’re so elegant, and so I’m going to focus here on the practical programming problem.”

I’m interested in both aspects of your graphs. Could you make an article about the colors you use, etc?

Thanks!

19. lode says:

SVG is definitely worth it. Better still, you can write your data in XML and use an XSLT to transform that into SVG.

20. 0x69 says:

Another option if you really want to control every pixel of graph - is to make PPM image file directly from LISP. PPM format is trivial and can be formated as ASCII text of RGB values:
http://en.wikipedia.org/wiki/Netpbm_format#PPM_example
The only problem i see here that ppm is not popular enough to be supported by browsers. But we can always use some graphics processing program (lets say GIMP) to convert PPM to PNG/JPG /other format.


text:
# BCs System

## Boundary Condition

• A BoundaryCondition provides a residual (and optionally a Jacobian) on a boundary (or internal side) of a domain.

• The structure is very similar to Kernels

• computeQpResidual/Jacobian()

• Parameters

• Coupling

• The only difference is that some BCs are NOT integrated over the boundary... and instead specify values on Boundaries (Dirichlet).

• BCs which are integrated over the boundary inherit from IntegratedBC.

• Non-integrated BCs inherit from NodalBC.

## (Some) Values Available to BCs

Integrated BCs:

• _u, _grad_u : Value and gradient of the variable this BC is operating on.

• _phi, _grad_phi : Value () and gradient () of the trial function.

• _test,_grad_test : Value () and gradient () of the test function.

• _q_point : XYZ coordinates

• _i, _j : test and trial shape function indices.

• _qp : Current quadrature point index.

• _normals : Normal vector.

• _boundary_id : The boundary ID.

• _current_elem : A pointer to the element.

• _current_side : The side number of _current_elem

Non-integrated BCs:

• _u

• _qp

• _boundary_id

• _current_node : A pointer to the current node that is being operated on.

## Coupling and BCs

The coupling of values and gradients into BCs is done the same way as in Kernels and materials :

• coupledValue()

• coupledValueOld()

• coupledValueOlder()

• coupledGradient()

• coupledGradientOld()

• coupledGradientOlder()

• coupledDot()

## Dirichlet BCs

• Set a condition on the value of a variable on a boundary.

• Usually... these are NOT integrated over the boundary.

Becomes:

• In the following example:

And therefore:

## Integrated BCs

• Integrated BCs (including Neumann BCs) are actually integrated over the external face of an element.

• Their residuals lokk similar to kernels. Thus

Becomes:

• Also note that if , then the boundary integral is zero (sometimes known os the "natural boundary condition").

## Example 4

Look at Example 4

## Periodic BCs

• Periodic boundary conditions are useful for modeling quasi-infinite domains and systems with conserved quantities.

• MOOSE has full support for periodic BCs

• 1D, 2D and 3D.

• Can be restricted to specific variables.

• Supports arbitrary translation vectors for defining periodicity.

[BCs]
[./Periodic]
[./all]
variable = u

#Works for any regular orthogonal
#mesh with defined boundaries
auto_direction = 'x y'
[../]
[../]
[]

[BCs]
[./Periodic]
[./x]
primary = 1
secondary = 4
transform_func = 'tr_x tr_y'
inv_transform_func = 'itr_x itr_y'
[../]
[../]
[]

• Normal usage: with an axis-aligned mesh, use auto-direction to supply the coordinate direction to wrap.

• Advanced usage: specify a translation or transformation function.

[BCs]
[./Periodic]
[./x]
variable = u
primary = 'left'
secondary = 'right'
translation = '10 0 0'
[../]
[../]
[]

## Periodic Example

Look at Example 4 Periodic Example

## Further BCs documentation

• Moose App
• ConvectiveFluxBCDetermines boundary values via the initial and final values, flux, and exposure duration
• DGFunctionDiffusionDirichletBC
• DiffusionFluxBCComputes a boundary residual contribution consistent with the Diffusion Kernel. Does not impose a boundary condition; instead computes the boundary contribution corresponding to the current value of grad(u) and accumulates it in the residual vector.
• DirichletBCImposes the essential boundary condition , where is a constant, controllable value.
• EigenDirichletBCDirichlet BC for eigenvalue solvers
• FunctionDirichletBCImposes the essential boundary condition , where is a (possibly) time and space-dependent MOOSE Function.
• FunctionNeumannBCImposes the integrated boundary condition , where is a (possibly) time and space-dependent MOOSE Function.
• FunctionPenaltyDirichletBC
• FunctionPresetBCThe same as FunctionDirichletBC except the value is applied before the solve begins
• LagrangeVecDirichletBCImposes the essential boundary condition , where are constant, controllable values.
• LagrangeVecFunctionDirichletBCImposes the essential boundary condition , where components are calculated with functions.
• MatchedValueBCImplements a NodalBC which equates two different Variables' values on a specified boundary.
• NeumannBCImposes the integrated boundary condition , where is a constant, controllable value.
• OneDEqualValueConstraintBC
• PenaltyDirichletBCEnforces a Dirichlet boundary condition in a weak sense by penalizing differences between the current solution and the Dirichlet data.
• PostprocessorDirichletBC
• PostprocessorNeumannBC
• PresetBCSimilar to DirichletBC except the value is applied before the solve begins
• SinDirichletBCImposes a time-varying essential boundary condition , where varies from an given initial value at time to a given final value over a specified duration.
• SinNeumannBCImposes a time-varying flux boundary condition , where varies from an given initial value at time to a given final value over a specified duration.
• VacuumBC
• VectorNeumannBCImposes the integrated boundary condition , where is a user-defined, constant vector.
• WeakGradientBCComputes a boundary residual contribution consistent with the Diffusion Kernel. Does not impose a boundary condition; instead computes the boundary contribution corresponding to the current value of grad(u) and accumulates it in the residual vector.
• Rdg App
• AEFVBCA boundary condition kernel for the advection equation using a cell-centered finite volume method.
• Functional Expansion Tools App
• FXFluxBCSets a flux boundary condition, evaluated using a FunctionSeries instance. This does not fix the flux, but rather 'strongly encourages' flux agreement by penalizing the differences through contributions to the residual.
• FXValueBCImposes a fixed value boundary condition, evaluated using a FunctionSeries instance.
• FXValuePenaltyBCSets a value boundary condition, evaluated using a FunctionSeries instance. This does not fix the value, but rather 'strongly encourages' value agreement by penalizing the differences through contributions to the residual.
• XFEMApp
• CrackTipEnrichmentCutOffBCSimilar to DirichletBC except the value is applied before the solve begins
• Heat Conduction App
• ConvectiveFluxFunctionDetermines boundary value by fluid heat transfer coefficient and far-field temperature
• CoupledConvectiveFlux
• CoupledConvectiveHeatFluxBCConvective heat transfer boundary condition with temperature and heat transfer coefficent given by auxiliary variables.
• GapHeatTransferTransfers heat across a gap between two surfaces dependant on the gap geometry specified.
• HeatConductionBC
• Tensor Mechanics App
• CoupledPressureBCApplies a pressure from a variable on a given boundary in a given direction
• DashpotBC
• DisplacementAboutAxisImplements a boundary condition that enforces rotationaldisplacement around an axis on a boundary
• InteractionIntegralBenchmarkBC
• PresetAccelerationPrescribe acceleration on a given boundary in a given direction
• PresetDisplacementPrescribe the displacement on a given boundary in a given direction.
• PresetVelocity
• PressureApplies a pressure on a given boundary in a given direction
• StickyBCImposes the boundary condition if exceeds the bounds provided
• Navier Stokes App
• EnergyFreeBC
• INSMomentumNoBCBCLaplaceFormThis class implements the 'No BC' boundary condition based on the 'Laplace' form of the viscous stress tensor.
• INSMomentumNoBCBCTractionFormThis class implements the 'No BC' boundary condition based on the 'traction' form of the viscous stress tensor.
• INSTemperatureNoBCBCThis class implements the 'No BC' boundary condition discussed by Griffiths, Papanastiou, and others.
• ImplicitNeumannBCThis class implements a form of the Neumann boundary condition in which the boundary term is treated 'implicitly'.
• MassFreeBC
• MomentumFreeBC
• MomentumFreeSlipBC
• NSEnergyInviscidSpecifiedBCThis class corresponds to the inviscid part of the 'natural' boundary condition for the energy equation.
• NSEnergyInviscidSpecifiedDensityAndVelocityBCThis class corresponds to the inviscid part of the 'natural' boundary condition for the energy equation.
• NSEnergyInviscidSpecifiedNormalFlowBCThis class corresponds to the inviscid part of the 'natural' boundary condition for the energy equation.
• NSEnergyInviscidSpecifiedPressureBCThis class corresponds to the inviscid part of the 'natural' boundary condition for the energy equation.
• NSEnergyInviscidUnspecifiedBCThis class corresponds to the inviscid part of the 'natural' boundary condition for the energy equation.
• NSEnergyViscousBCThis class couples together all the variables for the compressible Navier-Stokes equations to allow them to be used in derived IntegratedBC classes.
• NSEnergyWeakStagnationBCThe inviscid energy BC term with specified normal flow.
• NSImposedVelocityBCImpose Velocity BC.
• NSImposedVelocityDirectionBCThis class imposes a velocity direction component as a Dirichlet condition on the appropriate momentum equation.
• NSInflowThermalBCThis class is used on a boundary where the incoming flow values (rho, u, v, T) are all completely specified.
• NSMassSpecifiedNormalFlowBCThis class implements the mass equation boundary term with a specified value of rho*(u.n) imposed weakly.
• NSMassUnspecifiedNormalFlowBCThis class implements the mass equation boundary term with the rho*(u.n) boundary integral computed implicitly.
• NSMassWeakStagnationBCThe inviscid energy BC term with specified normal flow.
• NSMomentumConvectiveWeakStagnationBCThe convective part (sans pressure term) of the momentum equation boundary integral evaluated at specified stagnation temperature, stagnation pressure, and flow direction values.
• NSMomentumInviscidNoPressureImplicitFlowBCMomentum equation boundary condition used when pressure is not integrated by parts.
• NSMomentumInviscidSpecifiedNormalFlowBCMomentum equation boundary condition in which pressure is specified (given) and the value of the convective part is allowed to vary (is computed implicitly).
• NSMomentumInviscidSpecifiedPressureBCMomentum equation boundary condition in which pressure is specified (given) and the value of the convective part is allowed to vary (is computed implicitly).
• NSMomentumPressureWeakStagnationBCThis class implements the pressure term of the momentum equation boundary integral for use in weak stagnation boundary conditions.
• NSMomentumViscousBCThis class corresponds to the viscous part of the 'natural' boundary condition for the momentum equations.
• NSPenalizedNormalFlowBCThis class penalizes the the value of u.n on the boundary so that it matches some desired value.
• NSPressureNeumannBCThis kernel is appropriate for use with a 'zero normal flow' boundary condition in the context of the Euler equations.
• NSStagnationPressureBCThis Dirichlet condition imposes the condition p_0 = p_0_desired.
• NSStagnationTemperatureBCThis Dirichlet condition imposes the condition T_0 = T_0_desired.
• NSThermalBCNS thermal BC.
• Chemical Reactions App
• ChemicalOutFlowBCChemical flux boundary condition
• Porous Flow App
• PorousFlowHalfCubicSinkApplies a flux sink to a boundary. The base flux defined by PorousFlowSink is multiplied by a cubic.
• PorousFlowHalfGaussianSinkApplies a flux sink to a boundary. The base flux defined by PorousFlowSink is multiplied by a Gaussian.
• PorousFlowPiecewiseLinearSinkApplies a flux sink to a boundary. The base flux defined by PorousFlowSink is multiplied by a piecewise linear function.
• PorousFlowSinkApplies a flux sink to a boundary.


text:
作者：Damien Calaque 来源：[J].Annales de la faculté des sciences de Toulouse, 2019, Vol.28 (1), pp.67-90CEDRAM 摘要：We prove that shifted cotangent stacks carry a canonical shifted symplectic structure. We also prove that shifted conormal stacks carry a canonical Lagrangian structure. These results were believed to be true, but no written proof was available in the Artin case.
 作者：Nicolas Lerner 来源：[J].Annales de la faculté des sciences de Toulouse, 2019, Vol.28 (1), pp.1-9CEDRAM 摘要：The mathematician Yuri Egorov died on October 6, 2018 in Toulouse. This text outlines two fundamental aspects of his work, the quantification of canonical transformations and the study of subelliptic operators.
 作者：ShengYuan Zhao 来源：[J].Annales de la faculté des sciences de Toulouse, 2019, Vol.28 (1), pp.109-127CEDRAM 摘要：We study dynamical degree $>1$ real automorphisms of compact complex surfaces with a real structure. We show that a surface with such an automorphism is necessarily projective. We classify real abelian surfaces into eight types, according to the number of connected components of ...
 作者：Jakob Hultgren 来源：[J].Annales de la faculté des sciences de Toulouse, 2019, Vol.28 (1), pp.11-65CEDRAM 摘要：Inspired by constructions in complex geometry we introduce a thermodynamic framework for Monge–Ampère equations on real tori. We show convergence in law of the associated point processes and explain connections to complex Monge–Ampère equations on abelian varieties and ...
 作者：Matthias Gorny 来源：[J].Annales de la faculté des sciences de Toulouse, 2019, Vol.28 (1), pp.91-108CEDRAM 摘要：We build and study a multidimensional version of the Curie-Weiss model of self-organized criticality we have designed in [2]. For symmetric distributions satisfying some integrability condition, we prove that the sum $S_n$ of the randoms vectors in the model has a typical critica...
 作者：Didier Arnal , Mouna Chaabouni , Mabrouka Hfaiedh 来源：[J].Annales de la faculté des sciences de Toulouse, 2019, Vol.28 (1), pp.129-143CEDRAM 摘要：In this paper, we study the restriction of the Kontsevich formality to the subalgebra of the linear polyvectors in the algebra of polyvector fields on $\mathbb{R}^d$. We prove that this formality is an analytic map.
 作者：Stéphane Lamy 来源：[J].Annales de la faculté des sciences de Toulouse, 2019, Vol.28 (1), pp.145-207CEDRAM 摘要：We study the group $\mathrm{Tame}(\mathbb{A}^3)$ of tame automorphisms of the 3-dimensional affine space, over a field of characteristic zero. We recover, in a unified way, previous results of Kuroda, Shestakov, Umirbaev and Wright, about the theory of reduction and the relations...
 作者：Mathieu Lewin , Elliott H. Lieb , Robert Seiringer 来源：[J].CEDRAM 摘要：In this paper we define and study the classical Uniform Electron Gas (UEG), a system of infinitely many electrons whose density is constant everywhere in space. The UEG is defined differently from Jellium, which has a positive constant background but no constraint on the density....
 作者：Stéphane Druel , Henri Guenancia 来源：[J].CEDRAM 摘要：In this paper we show that any smoothable complex projective variety, smooth in codimension two, with klt singularities and numerically trivial canonical class admits a finite cover, étale in codimension one, that decomposes as a product of an abelian variety, and singular a...
 作者：Delphine Pol 来源：[J].Annales de l'institut Fourier(IF 0.527), 2018, Vol.68 (2), pp.725-766CEDRAM 摘要：We consider the germ of a reduced curve, possibly reducible. F. Delgado de la Mata proved that such a curve is Gorenstein if and only if its semigroup of values is symmetrical. We extend here this symmetry property to any fractional ideal of a Gorenstein curve. We then focus...


text:
Tag Info

8

Module works different than scoping constructs in other languages. Here's a simpler example which already gives a clue of what happens: x=3; Module[{x}, {x, Globalx, Context[x]}] (* ==> {x$81, x$81, Global} *) You see, no matter whether you prefix it with Global, x gets replaced with x$81, which indeed also has global context. Indeed, this is how ... 8 I recently realised that the Replace function essentially solves this problem, but it is not the sort of function you tend to associate with conditional constructs. It also might surprise readers of the code, as it is not a common idiom. This solution is: Replace[expr, {pat1 :> val1, pat2 :> val2, _ :> valD}] e.g. Replace[x, ... 5 For the first example Repeated, as already shown by Ymareth, is the simplest method: MatchQ[ {1, 2/3, 3.14, 4, 5.0, "x", "y"}, {Repeated[_?NumericQ, {5}], _, _} ] True For the case of arbitrary positions it seems to me that there are two natural approaches: Method 1: Build a pattern You can programmatically build a pattern like the one shown in ... 3 I like your elegant answer, and... Switch[#, pat : _Integer /; (val = pat; True), Print[val, " is integer"], pat : _Real /; (val = pat; True), Print[val, " is real"], pat_ /; (val = pat; True), Print[val, " is none of the above"]] & /@ {1, 1.1, a} (* 1 is integer 1.1 is real a is none of the above *) 3 list = {1,3,2,0,1,0,1,2,0,1,1,4,0}; MatchQ[list, {PatternSequence[1, ___?(IntegerQ@# && Positive[#] &), 0] ...}] True This is an interesting problem. I'm not sure how to solve it using Condition rather than PatternTest. 3 If lists are large, something like list1[[;; (Position[list1, Except[0 |0.| Null], 1][[-1, 1]])]] should be quite a bit faster, e.g., a quick test on a 50K length list it is over 350X faster than the rule-based solution, and 4X faster than the Take solution. If the list is "front-loaded" with values (i.e., more wanted than not), using list1[[;; ... 3 What's happening only indirectly involves the pattern matching. Mathematica, when dealing with operations that are Orderless, will put the arguments into a canonical ordering (described here). In this case, an expression like Subscript[Z, 2, 1] Subscript[Z, 3, 1] can be seen to be equivalent to Times[Subscript[Z,2,1], Subscript[Z,3,1]] using FullForm. ... 3 Jump straight down to Update 2 for the final code. I'll leave the previous iterations here as they explain how that solution developed. This is based on the following definition of similarity: Two expressions are similar if they become identical when all variables are replaced by the same generic variable. For example, both$a+b$and$b+c\$ become ...

3

A very interesting question. I thought of a much plainer approach than the other responders but it proves to perform quite well. I simply PadRight the reference sequence to match the length of the test sequence. Functions cycQ[ref_][test_] := test === PadRight[ref, Length @ test, ref] cycpat[f_, r___] := p : PatternSequence[f, ___] /; cycQ[{f, r}][{p}] ...

2

You say you want to be able to decide which columns have to be numeric and which ones don't. There are many approaches that aren't based on patterns and this is probably not the best one, but it will do the job. Let's define checkNumericColumns[entry_, blanks_] := Module[{shouldBeNumeric, areNumeric}, shouldBeNumeric = Complement[Range@Length@entry, ...

1

data = {I (a^2 + b^2) (*1*), a (I b + e) (*2*), b (I a + d) (*3*), b (I a + f) (*4*), a b (*5*), a (I b + f) (*6*), I (b^2 + c^2) (*7*)} systemnames = Names["System*"]; test[expr_] := Select[{Extract[expr, #], #} & /@ Position[expr, _Symbol, Infinity], MemberQ[systemnames , ToString@(#[[1]])] &] Gather[data, test[#1] == test[#2] ...

1

For the case with non numerical columns that are allowed. sel[dat_, nonNum_] := With[{n = Length@dat[[1]]}, Pick[ dat, And @@@ Map[NumericQ, dat[[;; , DeleteCases[Range[n], Alternatives @@ nonNum]]], {2}] ] ] so for the edit test: sel[mydataset, {2}] {{1, 2, 3, 4}, {3, 4, 5, 4}, {1, "", 3, 4}, {10, "", 12, 13}}

Only top voted, non community-wiki answers of a minimum length are eligible


text:
Functions in R are bundled in and so-called “packages”. A basic installation of R already comes with a certain collection of base packages, which are separately stored in the “System Library”. No matter how fundemental or basic the function, it is always part of a package, even though often not immediately realised. For example, the common function to print something to the R console print() is part of the base package (see topmost line in ?print, which states “print {base}”).

When starting R (or rather RStudio) all these base functions like print() or sum() are immediately available to the user. This is because all packages in the System Library are automatically loaded when starting R. A great advantage of R, however, is that its functionality can be greatly expanded by sharing and including custom packages. After installing a package (like e.g. the Luminescence package) its functions are not immediately available to the user when starting R. When we call a function of a package that is not yet loaded we get an error message like the following:

calc_CentralDose()
## Error in calc_CentralDose(): could not find function "calc_CentralDose"

Instead, we have to explicitly load the package first so that R can actually find the function. The common way to do this is by using the function library(), which only requires the name of the package to be loaded.

library(Luminescence)
## Loading required package: magrittr
## Welcome to the R package Luminescence version 0.8.1 [Built: 2018-02-14 08:20:54 UTC]
## A motivated R-Team member: 'We are doing this not just for statistical reasons, there is real science behind it!'

Explicitly loading a package is always necessary after starting R, unless the package was installed in the System Library (which is not the default behaviour and another topic for another time).

Occassionally, you will also see the function require() used to load a library. While both functions essentially do the same thing, there are fine nuances to the differences between both functions that particularly favor the use of the library() function.


text:
# Sum of n terms of series $(n^2-1^2)$ + $2\;.(n^2-2^2)$ + $3\;.(n^2-3^2)$+.....is

$(a)\;0\qquad(b)\;2n\;(n^2-1)\qquad(c)\;\frac{1}{4}\;n^2\;(n^2-1)\qquad(d)\;\frac{1}{4}\;n\;(n+1)^2$

Answer : (c) $\;\frac{1}{4}\;n^2\;(n^2-1)$
Explanation : $\;a_{r}=r\;(n-r)\;(n+r)$
$=n^2r-r^3$
$S_{n}=n^2\;\sum_{r=1}^{n}\;r-\sum_{r=1}^{n}\;r^3$
$=n^2\;\large\frac{n(n+1)}{2}-\large\frac{n^2(n+1)^2}{4}$
$=\large\frac{n^2(n+1)}{2}\;[n-\frac{n+1}{2}]$
$=\frac{1}{4}\;n^2\;(n^2-1)\;.$


text:
# [QGIS Commit] r8927 - docs/trunk/english_us/user_guide

svn_qgis at osgeo.org svn_qgis at osgeo.org
Sun Jul 27 00:49:40 EDT 2008

Author: taraathan
Date: 2008-07-27 00:49:40 -0400 (Sun, 27 Jul 2008)
New Revision: 8927

Modified:
docs/trunk/english_us/user_guide/working_with_vector.tex
Log:
replaced usage of the macros \fieldname and \sqltable with appropriate macros

Modified: docs/trunk/english_us/user_guide/working_with_vector.tex
===================================================================
--- docs/trunk/english_us/user_guide/working_with_vector.tex	2008-07-27 04:47:09 UTC (rev 8926)
+++ docs/trunk/english_us/user_guide/working_with_vector.tex	2008-07-27 04:49:40 UTC (rev 8927)
@@ -121,7 +121,7 @@

To load a MapInfo layer, click on the \toolbtntwo{addshapefile}{Add a vector layer}
toolbar bar button or type \keystroke{V}, change the file type filter to
-\fieldname{MapInfo (*.mif
+\selectstring{File Type}{MapInfo (*.mif
*.tab *.MIF *.TAB)} and select the layer you want to load.

@@ -132,7 +132,7 @@
toolbar button or type \keystroke{V} to open the
\dialog{Open on OGR Supported Vector Layer}
dialog and change the file type filter to
-\fieldname{All files (*.*)}. Navigate to the coverage directory and select one
+\selectstring{File Type}{All files (*.*)}. Navigate to the coverage directory and select one
of the following files (if present in your coverage):

\begin{itemize}
@@ -159,7 +159,8 @@
\item Connect to the database.
\item Select the layer to add to the map.
-\item Optionally provide a SQL \sqltable{where} clause to define which features
+\item Optionally provide a SQL \usertext{where}
+clause to define which features
to load from the layer.
\item Load the layer.
\end{itemize}
@@ -459,8 +460,8 @@

The \tab{Metadata} tab contains information about the layer, including specifics
about the type and location, number of features, feature type, and the editing
-capabilities. The \fieldname{projection} and \fieldname{attribute} fields and
-their data type are displayed
+capabilities. The \guiheading{Layer Spatial Reference System} section, providing projection information, and the \guiheading{Attribute field info} section,
+listing fields and their data types, are displayed
on this tab. This is a quick way to get information about the layer.

\subsubsection{Labels Tab}
@@ -478,9 +479,10 @@
\item Open the \dialog{Layer Properties} dialog.
\item Click on the \tab{Labels} tab.
\item Check the \checkbox{Display labels} checkbox to enable labeling.
-\item Choose the field to label with. We'll use \fieldname{NAMES}.
+\item Choose the field to label with.
+  We'll use \selectstring{Field containing labels}{NAMES}.
\item Enter a default for lakes that have no name. The default label will be
-  used each time QGIS encounters a lake with no value in the \fieldname{NAMES} field.
+  used each time QGIS encounters a lake with no value in the \guilabel{NAMES} field.
\item Click \button{Apply}.
\end{enumerate}

@@ -566,7 +568,7 @@

In the first example, the web browser konqueror is invoked and passed a URL to
-open. The URL performs a Google search on the value of the \fieldname{nam} field
+open. The URL performs a Google search on the value of the \usertext{nam} field
from our vector layer. Note that the application or script called by the
action must be in the path or you must provided the full path. To be sure, we could
rewrite the first example as: \usertext{/opt/kde3/bin/konqueror
@@ -592,8 +594,8 @@
Here is another example that pulls data out of a vector layer and inserts them
into a file using bash and the \usertext{echo} command (so it will only work
\nix or perhaps \osx). The layer in question has fields for a species name
-\fieldname{taxon\_name}, latitude \fieldname{lat} and longitude
-\fieldname{long}. I would like to be able to
+\usertext{taxon\_name}, latitude \usertext{lat} and longitude
+\usertext{long}. I would like to be able to
make a spatial selection of a localities and export these field values to a
text file for the selected record (shown in yellow in the QGIS map area). Here is
the action to achieve this:
@@ -617,7 +619,7 @@
keyword. This is easily done by just going to Google and doing a simple
search, then grabbing the URL from the address bar in your browser. From this
little effort we see that the format is: \url{http://google.com/search?q=qgis},
-where \fieldname{qgis} is the search term. Armed with this information, we can
+where \usertext{qgis} is the search term. Armed with this information, we can
proceed:

\begin{itemize}
@@ -632,12 +634,12 @@
\item Following the name of the external application, add the URL used for
doing a Google search, up to but not included the search term:
-\item The text in the \fieldname{Action} field should now look like this:\\
+\item The text in the \guilabel{Action} field should now look like this:\\
\item Click on the drop-down box containing the field names for the
-  \fieldname{lakes} layer. It's located just to the right of the
+  \usertext{lakes} layer. It's located just to the right of the
\button{Insert Field} button.
-\item From the drop-down box, select \fieldname{NAMES} and click \button{Insert Field}.
+\item From the drop-down box, select \selectstring{}{NAMES} and click \button{Insert Field}.
\item Your action text now looks like this:\\ \usertext{firefox
\end{itemize}
@@ -1064,7 +1066,7 @@

To complete the creation of the new layer, add the desired attributes by
clicking on the \button{Add} button and specifying a name and type for the
-attribute. Only \fieldname{real}, \fieldname{integer}, and \fieldname{string} attributes are supported. Once you
+attribute. Only \selectstring{Type}{real}, \selectstring{Type}{integer}, and \selectstring{Type}{string} attributes are supported. Once you
are happy with the attributes, click \button{OK} and provide a name for the shapefile.
QGIS will automatically add a \filename{.shp} extension to the name you specify.  Once
the layer has been created, it will be added to the map and you can edit it in
@@ -1076,8 +1078,8 @@
The Query Builder allows you to define a subset of a table and display
it as a layer in QGIS. It can be used for all OGR supported formats, GRASS
files and PostGIS layers. For example, if you have a \filename{towns} layer with a
-\fieldname{population} field you could select only larger towns by entering
-\sqltable{population > 100000} in the SQL box of the query builder. Figure
+\usertext{population} field you could select only larger towns by entering
+\usertext{population > 100000} in the SQL box of the query builder. Figure
\ref{fig:query_builder} shows an example of the query builder populated with
data from a PostGIS layer with attributes stored in PostgreSQL.


text:
# A finite subset of a Boolean algebra, generates a finite subalgebra.

Let $\mathscr{B}$ be a Boolean algebra and let $F$ be a finite subset of $\mathscr{B}$. Is $\left<F\right>$, the subalgebra generated by $F$, necessarily a finite subalgebra of $\mathscr{B}$?

I thinks that this is true based on following argument: Denote the elements of $F$ by $x_1,\ldots,x_n$, and consider the $2^n$ possible ways of forming $\land$(meet) of $n$ elements $x_{1}^{e_1},\ldots,x_{i}^{e_i},\ldots x_{n}^{e_n}$ where each $e_i$ can be either the empty word, or the complement symbol '. Let $A$ be the subset of $\mathscr{B}$ having just those $2^n$ values. Some of these $2^n$ ways might yield same elements of $\mathscr{B}$, hence we have a subset $A$ of $\mathscr{B}$ with at most $2^n$ elements. Then $\left<F\right>$ is isomorphic to $\mathscr{P}(A)$, the Boolean algebra of subsets of a set having $|A|$ elements.

I came up with this idea while pondering upon the image of a venn diagram with $n$ circles. I think that this argument is valid, and can be completed in a rigorous way, but I am not sure. Is this a valid argument? Is the statement true?

The statement is right, but your proof is not correct. For example, suppose $F=\{x_1, x_2\}$ with $x_1< x_2$ (that is, $x_1\not=x_2$ and $x_1\vee x_2=x_2$).
Then the $A$ we get consists of $$a_1=x_1\wedge x_2,\quad a_2=x_1\wedge x_2', \quad a_3=x_1'\wedge x_2,\quad a_4=x_1'\wedge x_2'.$$ But distinct elements of the powerset of $A$ do not necessarily correspond to distinct elements of $\langle F\rangle$! Namely, both $\emptyset$ and $\{a_3\}$ correspond to $\bot$, since $x_1<x_2$.
So really, the right statement is that $\langle F\rangle$ is a homomorphic image, or quotient, of $\mathcal{P}(A)$.
• But isn't it true that $\left<F\right>$ is isomorphic to $\mathscr{P}(A)$?. I believe your point is that the $A$ I constructed has no reason to be a subalgebra. But I guess they are the atoms of $\left<F\right>$ so that $\left<F\right>$ is a finite Boolean algebra with $|A|$ atoms... thus isomorphic to $\mathscr{P}(A). – Dilemian Dec 22 '16 at 10:51 • @Dilemian I misread, and have edited my answer. There's still a problem, though:$P(A)$might be bigger than$\langle F\rangle$. – Noah Schweber Dec 22 '16 at 20:21 The free Boolean ring on$n$generators is nothing more than the polynomial ring$\mathbb{F}_2[x_1,x_2,\dots,x_n]$modulo the ideal generated by$x_i^2-x_i$, for$i=1,2,\dots n$, so it's essentially the set of linear combinations of monomials having degree at most$1$in each variable, with coefficients in$\mathbb{F}_2$; there are$2^n$such monomials, so the free Boolean ring on$n$generators has$2^{2^n}$elements. Since Boolean rings and Boolean algebras are the same thing, the free Boolean algebra on$n$generators is finite. The subalgebra generated by$F$is a homomorphic image of a free algebra on$|F|$generators, so it is finite as well. Note that the homomorphism need not be injective; for instance, the Boolean subalgebra of$A=\mathscr{P}(\{1,2\})$generated by$\{1\}$and$\{2\}$is$A$itself, but the free algebra on two elements has$16$elements. The fact is that between elements of$F$there can be nontrivial relations, in this case$\{2\}$is the complement of$\{1\}$. • That's a neat argument. I never realized that the perspective of Boolean rings made free Boolean algebras so simple to describe. – Eric Wofsey Dec 22 '16 at 21:16 • @EricWofsey I always get lost with prenex form and the like, so I just switch to rings which I'm more familiar with. – egreg Dec 22 '16 at 21:28 For finite$m$and$n,$an$n$-generated Boolean algebra has at most$2^n$atoms, and a finite Boolean algebra with$m$atoms has exactly$2^m$elements. A free Boolean algebra on$n$generators has exactly$2^n$atoms (which you described) and exactly$2^{2^n}\$ elements.


text:
Version 21 (modified by antonio, 5 years ago) (diff)

--

# The Sandbox

This is just a page to practice and learn WikiFormatting.

This has a pointer.

### [[TOC]]

Generate a table of contents for the current page or a set of pages. If no arguments are given, a table of contents is generated for the current page, with the top-level title stripped:

    [[TOC]]

To generate a table of contents for a set of pages, simply pass them as comma separated arguments to the TOC macro, e.g. as in

[[TOC(TracGuide, TracInstall, TracUpgrade, TracIni, TracAdmin, TracBackup,
TracLogging, TracPermissions, TracWiki, WikiFormatting, TracBrowser,

A wildcard '*' can be used to fetch a sorted list of all pages starting with the preceding pagename stub:

[[TOC(Trac*, WikiFormatting, WikiMacros)]]

The following control arguments change the default behaviour of the TOC macro:

 Argument Meaning heading= Override the default heading of "Table of Contents" noheading Suppress display of the heading. depth= Display headings of subsequent pages to a maximum depth of . inline Display TOC inline rather than as a side-bar. sectionindex Only display the page name and title of each page in the wiki section. titleindex Only display the page name and title of each page, similar to TitleIndex. notitle Supress display of page title.

For 'titleindex' argument, an empty pagelist will evaluate to all pages:

[[TOC(titleindex, notitle, heading=All pages)]]

'sectionindex' allows to generate a title index for all pages in a given section of the wiki. A section is defined by wiki page name, using '/' as a section level delimiter (like directories in a file system). Giving '/' or '*' as the page name produces the same result as 'titleindex' (title of all pages). If a page name ends with a '/', only children of this page will be processed. Else the page given in the argument is also included, if it exists. For 'sectionindex' argument, an empty pagelist will evaluate to all page below the same parent as the current page:

[[TOC(sectionindex, notitle, heading=This section pages)]]

# Asciinerama

asciinema tango solarized-dark solarized-light monokai


text:
Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

E. Mahmoud and Ehab and the xor-MST
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Ehab is interested in the bitwise-xor operation and the special graphs. Mahmoud gave him a problem that combines both. He has a complete graph consisting of n vertices numbered from 0 to n - 1. For all 0 ≤ u < v < n, vertex u and vertex v are connected with an undirected edge that has weight (where is the bitwise-xor operation). Can you find the weight of the minimum spanning tree of that graph?

The weight of the minimum spanning tree is the sum of the weights on the edges included in it.

Input

The only line contains an integer n (2 ≤ n ≤ 1012), the number of vertices in the graph.

Output

The only line contains an integer x, the weight of the graph's minimum spanning tree.

Example
Input
4
Output
4
Note

In the first sample: The weight of the minimum spanning tree is 1+2+1=4.


text:
source:docs/HPCA2012/latex/egpaper_for_review.tex@1804

Last change on this file since 1804 was 1326, checked in by ashriram, 8 years ago

New Intro New title

File size: 17.0 KB
Line
1%&latex
2\documentclass[12pt,letterpaper]{article}
3\usepackage{setspace}
4\doublespacing
5\usepackage{iccv}
6\usepackage{times}
7\usepackage{epsfig}
8\usepackage{graphicx}
9\usepackage{amsmath}
10\usepackage{amssymb}
11
12% Include other packages here, before hyperref.
13
14% If you comment hyperref and then uncomment it, you should delete
15% egpaper.aux before re-running latex.  (Or just hit 'q' on the first latex
16% run, let it finish, and you should be clear).
18
19
20% \iccvfinalcopy % *** Uncomment this line for the final submission
21
22\def\iccvPaperID{****} % *** Enter the HPCA Paper ID here
23\def\httilde{\mbox{\tt\raisebox{-.5ex}{\symbol{126}}}}
24
25% Pages are numbered in submission mode, and unnumbered in camera-ready
26\ificcvfinal\pagestyle{empty}\fi
27\begin{document}
28
29%%%%%%%%% TITLE
30\title{\LaTeX\ Author Guidelines for HPCA Submissions}
31
32\author{First Author\\
33Institution1\\
35{\tt\small firstauthor@i1.org}
36% For a paper whose authors are all at the same institution,
37% omit the following lines up until the closing }''.
38% Additional authors and addresses can be added with \and'',
39% just like the second author.
41\and
42Second Author\\
43Institution2\\
45{\small\url{http://www.author.org/~second}}
46}
47
48\maketitle
49% \thispagestyle{empty}
50
51%%%%%%%%% ABSTRACT
52\begin{abstract}
53   The ABSTRACT is to be in fully-justified italicized text. Use the word Abstract'' as the title, in 14-point
54   Times, boldface type, centered relative to the column, initially
55   capitalized. The abstract is to be in 12-point, single-spaced type.
56   Leave two blank lines after the Abstract, then begin the main text.
57   Look at previous HPCA abstracts to get a feel for style and length.
58\end{abstract}
59
60%%%%%%%%% BODY TEXT
61\section{Introduction}
62
64HPCA\ for review.  \textit{This guide and style files are adapted with some revisions from the guide for ICCV\
65(International Conference on Computer Vision) submissions (http://www.iccv2011.org/paper-submission) and from the guide for MICRO 2011.
66}
67
68%-------------------------------------------------------------------------
69\subsection{Language}
70
71All manuscripts must be in English.
72
73\subsection{Dual submission}
74
75By submitting a manuscript to HPCA, the authors assert that it has not been previously published in substantially similar
76form.  Furthermore, no paper which contains significant overlap with the contributions of this paper either has been or will
77be submitted during the HPCA 2012 review period to \textbf{either} \textbf{a conference} (including HPCA 2012) or\textbf{
78a journal }(prior publication to IEEE Computer Architecture Letters is not considered a conflict).  Papers violating this
79condition will be rejected and further action will be taken with IEEE and ACM.
80
81If you have submitted any papers recently that may appear to the reviewers to violate this condition, then it is your
82responsibility to (1) cite these papers (preserving anonymity as described in Section 1.6 below), (2) argue in the body of
83your paper why your HPCA paper is nontrivially different from these concurrent submissions, and (3) include anonymized
84versions of those papers as supplemental material (provided that this functionality is present in the submission system at the time of submission -- if not, you do not have to submit this material).
85
86\subsection{Paper Length}
87\textbf{Submitted papers may have up to 28 pages.}.  Overlength papers will simply not be reviewed. This includes papers
88where the margins and formatting are deemed to have been significantly altered from those laid down by this style guide. Note that this \LaTeX\ guide already sets figure captions and references in a smaller font. There are two reasons why such papers will not be reviewed: (1)  There is no provision for supervised revisions of manuscripts. The reviewing process cannot determine the suitability of the paper for presentation in fewer pages than the submitted version. (2) Reviewing is hard work and is done on a volunteer basis on the spare'' time of the reviewers. Respect the reviewer's time by succinctly presenting your ideas and results in the reasonable amount of space that has been provisioned.
89
90%-------------------------------------------------------------------------
91\subsection{The Ruler}
92The \LaTeX\ style defines a printed ruler which should be present in the
93version submitted for review.  The ruler is provided in order that
94reviewers may comment on particular lines in the paper without
95circumlocution.  If you are preparing a document using a non-\LaTeX\
96document preparation system, please arrange for an equivalent ruler to
97appear on the final output pages.   {\bf Note to Reviewers:}
98note that the ruler measurements do not align well with lines in the paper
99--- this turns out to be very difficult to do well when the paper contains
100many figures and equations, and, when done, looks ugly.  The ruler uses single spacing making it easier to identify lines even under these situations.
101
102\subsection{Mathematics}
103
105important for readers to be able to refer to any particular equation.  Just
106because you didn't refer to it in the text doesn't mean some future reader
107might not need to refer to it.  It is cumbersome to have to use
108circumlocutions like the equation second from the top of page 3 column
1091''.  (Note that the ruler will not be present in the final copy, so is not
110an alternative to equation numbers).
111
112
113\subsection{Blind review}
114
115 Blind review does not mean that one must remove
116citations to one's own work---in fact it is often impossible to
117review a paper unless the previous citations are known and
118available.
119
120Blind review means that you do not use  words like  my'' or our''
121when citing previous work.  That is all.  (But see below for
122techreports)
123
124Saying this builds on the work of Lucy Smith [1]'' does not say
125that you are Lucy Smith, it says that you are building on her
126work.  If you are Smith and Jones, do not say as we show in
127[7]'', say as Smith and Jones show in [7]'' and at the end of the
128paper, include reference 7 as you would any other cited work.
129\textbf{Papers with improper self-references or that violate blind reviewing will be rejected.}
130
131An example of a \textbf{inappropriate} paper:
132\begin{quote}
133\begin{center}
134    An analysis of the frobnicatable foo filter.
135\end{center}
136
137   In this paper we present a performance analysis of our
138   previous paper [1], and show it to be inferior to all
139   previously known methods.  Why the previous paper was
140   accepted without this analysis is beyond me.
141
142   [1] Removed for blind review
143\end{quote}
144
145
146An example of an acceptable paper:
147
148\begin{quote}
149\begin{center}
150     An analysis of the frobnicatable foo filter.
151\end{center}
152
153   In this paper we present a performance analysis of the
154   paper of Smith \etal [1], and show it to be inferior to
155   all previously known methods.  Why the previous paper
156   was accepted without this analysis is beyond me.
157
158   [1] Smith, L and Jones, C. The frobnicatable foo
159   filter, a fundamental contribution to human knowledge''.
160   Nature 381(12), 1-213.
161\end{quote}
162
163
164
165Finally, you may feel you need to tell the reader that more details can be
166found elsewhere, and refer them to a technical report.  For conference
167submissions, the paper must stand on its own, and not {\em require} the
168reviewer to go to a techreport for further details.  Thus, you may say in
169the body of the paper further details may be found
170in~\cite{Authors11b}''.
171Again, you may not assume the reviewers will read this material.
172
173Sometimes your paper is about a problem which you tested using a tool which
174is widely known to be restricted to a single institution.  For example,
175let's say it's 1969, you have solved a key problem on the Apollo lander,
176and you believe that the HPCA 12 audience would like to hear about your
177solution.  The work is a development of your celebrated 1968 paper entitled
178Zero-g frobnication: How being the only people in the world with access to
179the Apollo lander source code makes us a wow at parties'', by Zeus \etal.
180
181You can handle this paper like any other.  Don't write We show how to
182improve our previous work [Anonymous, 1968].  This time we tested the
183algorithm on a lunar lander [name of lander removed for blind review]''.
184That would be silly, and would immediately identify the authors. Instead
185write the following:
186\begin{quotation}
187\noindent
188   We describe a system for zero-g frobnication.  This
189   system is new because it handles the following cases:
190   A, B.  Previous systems [Zeus et al. 1968] didn't
191   handle case B properly.  Ours handles it by including
192   a foo term in the bar integral.
193
194   ...
195
196   The proposed system was integrated with the Apollo
197   lunar lander, and went all the way to the moon, don't
198   you know.  It displayed the following behaviours
199   which show how well we solved cases A and B: ...
200\end{quotation}
201As you can see, the above text follows standard scientific convention,
202reads better than the first version, and does not explicitly name you as
203the authors.  A reviewer might think it likely that the new paper was
204written by Zeus \etal, but cannot make any decision based on that guess.
205He or she would have to be sure that no other authors could have been
206contracted to solve problem B.
207
208Do not include an acknowledgement  section in the submitted version.
209
210
211\begin{figure}[t]
212\begin{center}
213\fbox{\rule{0pt}{2in} \rule{0.9\linewidth}{0pt}}
214   %\includegraphics[width=0.8\linewidth]{egfigure.eps}
215\end{center}
216   \textsf{\caption{Example of caption.  }
217   \label{fig:long}
218   \label{fig:onecol}
219}
220
221\end{figure}
222
223\subsection{Miscellaneous}
224
225\noindent
226Compare the following:\\
227\begin{tabular}{ll}
228 \verb'$conf_a$' &  $conf_a$ \\
229 \verb'$\mathit{conf}_a$' & $\mathit{conf}_a$
230\end{tabular}\\
231See The \TeX book, p165.
232
233
234When citing a multi-author paper, you may save space by using et alia'',
235shortened to \etal'' (not {\em et.\ al.}'' as {\em et}'' is a complete word.)
236However, use it only when there are three or more authors.  Thus, the
237following is correct:
238   Frobnication has been trendy lately.
239   It was introduced by Alpher~\cite{Alpher02}, and subsequently developed by
240   Alpher and Fotheringham-Smythe~\cite{Alpher03}, and Alpher \etal~\cite{Alpher04}.''
241
242This is incorrect: ... subsequently developed by Alpher \etal~\cite{Alpher03} ...''
243because reference~\cite{Alpher03} has just two authors.  If you use the
244\verb'\etal' macro provided, then you need not worry about double periods
245when used at the end of a sentence as in Alpher \etal.
246
247For this citation style, keep multiple citations in numerical (not
248chronological) order, so prefer~\cite{Alpher02,Alpher03,Authors11}  to~\cite{Alpher03,Alpher02,Authors11}.
249
250
251\begin{figure*}
252\begin{center}
253\fbox{\rule{0pt}{2in} \rule{.9\linewidth}{0pt}}
254\end{center}
255   \textsf{
256       \caption{Example of a short caption, which should be centered.}
257       \label{fig:short}
258   }
259
260\end{figure*}
261
262%------------------------------------------------------------------------
264
265The submission must be printed in PDF\ format and for letter-sized paper ($8.5 \times 11$-inch). All text must be in a single-column format. The total allowable width of the
266text area is $6\frac78$ inches (17.5 cm) wide by $8\frac78$ inches (22.54
267cm) high.  The main title (on the
268first page) should begin 1.0 inch (2.54 cm) from the top edge of the
269page. The second and following pages should begin 1.0 inch (2.54 cm) from
270the top edge. On all pages, the bottom margin should be 1-1/8 inches (2.86
271cm) from the bottom edge of the page for $8.5 \times 11$-inch paper;
272
273%-------------------------------------------------------------------------
274\subsection{Margins and page numbering}
275
276All printed material, including text, illustrations, and charts, must be
277kept within a print area 6-7/8 inches (17.5 cm) wide by 8-7/8 inches
278(22.54 cm) high.
279
280
281%-------------------------------------------------------------------------
282\subsection{Type-style and fonts}
283
284Wherever Times is specified, Times Roman may also be used. If neither is
286appearance to Times to which you have access.
287
288MAIN TITLE. Center the title 1-3/8 inches (3.49 cm) from the top edge of
289the first page. The title should be in Times 14-point, boldface type.
290Capitalize the first letter of nouns, pronouns, verbs, adjectives, and
291adverbs; do not capitalize articles, coordinate conjunctions, or
292prepositions (unless the title begins with such a word). Leave two blank
293lines after the title.
294
295
296MAIN TEXT. Type main text in 12-point Times, double-spaced. All paragraphs should be indented 1 pica (approx. 1/6
297inch or 0.422 cm). Make sure your text is fully justified---that is,
298flush left and flush right. Please do not place any additional blank
299lines between paragraphs.
300
301Figure and table captions should be 10-point arial/sans serif (helvetica)\ type as in
302Figures~\ref{fig:onecol} and~\ref{fig:short}.  Short captions should be centred.
303
304\noindent Callouts should be 10-point Helvetica, non-boldface type.
305Initially capitalize only the first word of section titles and first-,
307
308Table contents should be in at least 10-point type.
309
310FIRST-ORDER HEADINGS. (For example, {\large \bf 1. Introduction})
311should be Times 14-point boldface, initially capitalized, flush left,
312with one blank line before, and one blank line after.
313
314SECOND-ORDER HEADINGS. (For example, { \bf 1.1. Database elements})
315should be Times 12-point boldface, initially capitalized, flush left,
316with one blank line before, and one after. If you require a third-order
317heading (we discourage it), use 12-point Times, boldface, initially
318capitalized, flush left, preceded by one blank line, followed by a period
319and your text on the same line.
320
321
322
323\subsection{Figure and Table References\\ }
324
325In order to get proper references to figure and table captions make sure to include the \textbackslash{label}\textbraceleft ...\textbraceright\ statement \textbf{with the} caption as follows:
326
327\verb'\begin{figure*}'\newline
328\verb'    ...'\newline
329\verb'    \textsf{'\newline
330\verb'       \caption{Caption text}'\newline
331\verb'       \label{fig:short} <--- must be in here'\newline
332\verb'   }'\newline
333\verb'\end{figure*}'
334
335
336\subsection{Tables}
337
338Use at least 12-pt font size for your tables, center them, and use the same caption style as that for figures.
339
340%-------------------------------------------------------------------------
341\subsection{Footnotes}
342
343Please use footnotes\footnote {This is what a footnote looks like.  It
344often distracts the reader from the main flow of the argument.} sparingly.
345Indeed, try to avoid footnotes altogether and include necessary peripheral
346observations in
347the text (within parentheses, if you prefer, as in this sentence).  If you
348wish to use a footnote, place it at the bottom of the column on the page on
349which it is referenced. Use Times 10-point type, single-spaced or double-spaced.
350
351
352%-------------------------------------------------------------------------
353\subsection{References}
354
355List and number all bibliographical references in 10-point Times,
356single-spaced or double-spaced, at the end of your paper. When referenced in the text,
357enclose the citation number in square brackets, for
358example~\cite{Authors11}.  Where appropriate, include the name(s) of
359editors of referenced books.
360
361\begin{table}
362\begin{center}
363\begin{tabular}{|l|c|}
364\hline
365Method & Frobnability \\
366\hline\hline
367Theirs & Frumpy \\
368Yours & Frobbly \\
369Ours & All of the Above\\
370\hline
371\end{tabular}
372\end{center}
373\textsf{\caption{Results.   Ours is better.}\label{iamthetable}}
374\end{table}
375
376%-------------------------------------------------------------------------
377\subsection{Illustrations, graphs, and photographs}
378
379All graphics should be centered.  Please ensure that any point you wish to
380make is resolvable in a printed copy of the paper.  Resize fonts in figures
381to match the font in the body text, and choose line widths which render
382effectively in print.  Many readers (and reviewers), even of an electronic
383copy, will choose to print your paper in order to read it.  You cannot
384insist that they do otherwise, and therefore must not assume that they can
385zoom in to see tiny details on a graphic.
386Do not use font sizes less than 9pt in figures.
387
388When placing figures in \LaTeX, it's almost always best to use
389\verb+\includegraphics+, and to specify the  figure width as a multiple of
390the line width as in the example below
391{\small\begin{verbatim}
392   \usepackage[dvips]{graphicx} ...
393   \includegraphics[width=0.8\linewidth]
394                   {myfile.eps}
395\end{verbatim}
396}
397
398
399%-------------------------------------------------------------------------
400\subsection{Color}
401
402Color is valuable, and will be visible to readers of the electronic copy.
403However ensure that, when printed on a monochrome printer, no important
404information is lost by the conversion to grayscale.
405
406%------------------------------------------------------------------------
407
408
409{\small
410\bibliographystyle{ieee}
411\bibliography{egbib}
412}
413
414
415\end{document}
Note: See TracBrowser for help on using the repository browser.