Useful diagnostics with CUDA 8 SSSP

CUDA 8 SSSP Tip:: When nvgraphSssp (part of the nvGraph library, new for CUDA 8) returns the “Not Converged” status, you *can* still call nvgraphGetVertexData to find the negative weight cycle(s) by examining costs and looking at which vertices have spiraling down in cost.

(Yes, nvgraphSssp works correctly in graphs with edges with negative weights, but no negative weight cycles.)

Happy Birthday, Bill! (in COBOL)

COBOL turned 50 a few years ago, and today is the birthday of the only person I know who programs in COBOL.  So, here’s a COBOL program, because I get really easily distracted.

      * Wish Bill a Happy Birthday if it's 05-06
      * Wish COBOL a Happy Birthday if it's 05-28.
      * Tell us how old COBOL is now (full years only)
      * Works for other people who share the same birthday, of course.
       IDENTIFICATION DIVISION.
       PROGRAM-ID. BillsBirthday.
       ENVIRONMENT DIVISION.
       DATA DIVISION.
       WORKING-STORAGE SECTION.
       01  TODAY.
           02  YYYY  PIC 9(4).
           02  MMDD  PIC 9(4).
       01  BILLBDAY.
           02  YYYY  PIC 9(4).
           02  MMDD  PIC 9(4) VALUE "0506".
       01  COBOLBDAY.
           02  YYYY  PIC 9(4) VALUE "1959".
           02  MMDD  PIC 9(4) VALUE "0528".
       01  AGE       PIC ZZ9.
       PROCEDURE DIVISION.
       MOVE FUNCTION CURRENT-DATE TO TODAY.
       IF MMDD OF COBOLBDAY <= MMDD OF TODAY THEN
         COMPUTE AGE = YYYY OF TODAY - YYYY OF COBOLBDAY
       ELSE
         COMPUTE AGE = YYYY OF TODAY - YYYY OF COBOLBDAY - 1
       END-IF.
       DISPLAY "COBOL has been around for " AGE " years."
       IF MMDD OF COBOLBDAY IS = MMDD OF TODAY THEN
         DISPLAY "Happy Birthday, COBOL!"
       END-IF.
       IF MMDD OF BILLBDAY IS = MMDD OF TODAY THEN
         DISPLAY "Happy Birthday, Bill!" 
       END-IF.
       STOP RUN.

To try it out, see opencobol.org

 

Cheating at Homework

#!/usr/bin/python
from nltk.corpus import wordnet 
shorts = "aceimnorsuvwxz" 
longs = "bdfhklt" 
for i1 in shorts: 
    for i2 in longs: 
        for i3 in shorts: 
            for i4 in shorts: 
                for i5 in shorts: 
                    wordinq = i1+i2+i3+i4+i5 
                    if i1=='a' or i3=='a' or i4=='a' or i5=='a': 
                        synsets = wordnet.synsets(wordinq) 
                        for synset in synsets: 
                            print wordinq+':', synset.definition 
                            break;

…is how to cheat at 3rd grade homework.

On Gremlins and Time Zones

“If you aren’t supposed to feed gremlins after midnight, when exactly can you start feeding them?  What about Daylight Savings Time and time zone issues?”

What do we know?

First of all, the instructions don’t say when they can eat again.

Second, I don’t think we know at what time the feeding was, just that the clock stopped a little after 11:35pm, that they were in NY, and that it was close enough to Christmas that Daylight Savings Time was not a factor.

Third, the instructions were not written by a legal team; they were passed on by the shopkeeper’s grandson who was selling the Mogwai against his grandfather’s wishes.

Finally, the creature must be able to survive in China and New York.

Any guesses on when they can start eating again should take into account that a second time in the instructions from the guy at the shop is not clearly necessary. If it’s 11:30am before you can feed them, that’s something you tell the average customer so they don’t have a nasty surprise over their Sunday waffles. It has to be fairly early in the morning to account for early risers, too, maybe 4am or astronomical dawn.  Both 4am and astronomical dawn occur before any normal family eating occurrences, so the grandson might not have felt obliged to mention this in the original instructions.

One might be tempted to consider what happens near the poles when there are months of day and months of night, but the more important thing to consider is that we have no reason to believe that Mogwai can live there in the first place. Maybe Mogwai would find polar winters uninhabitable.

So, why is food bad after midnight?  Midnight is important for two reasons: midnight is nearly opposite of the solar noon (astronomy), and midnight is typically marked by an absence of light in the parts of the Earth where Mogwai are reputed by the movies to exist (photobiology).

First hypothesis: it has something to do with the sun. Perhaps it’s not safe to go by Universal Coordinated Time or anything derived from it, and further experiments would show that sometimes it’s OK to feed Mogwai at 12:04am and sometimes 11:56pm would still cause problems. This is something we should have learned in the movie, if Billy or his science teacher hadn’t shown the same scientific rigor we see in some of Newton’s less impressive cronies. (This is not a compliment. Seriously, go look up what the Royal Society was doing in late 1600s sometime. Dead frogs abounded. Some of it was like Oddities for science.)

If the important Do-Not-Eat-After time used the word “midnight” to mean the opposite of solar noon instead of a time derived from a world standard, then the time when they’re allowed to eat again would also presumably involve more calculations than can be answered with a simple clock.

The old shopkeeper said that owning a Mogwai was too much responsibility, and any pet that requires an astrolabe or a computer to feed is more pet than most people should be buying for their son. “Mogwai” is Cantonese for devil or demon, but the word predates Christianity in China. These creatures aren’t related to Satan; these are creatures that are just enough of a nuisance that you would not sell one to Billy’s father because he’s kind of an idiot. Specifically, Billy’s father is the kind of idiot who buys an animal with these rules and doesn’t ask why the rules exist, the ramifications of failure to follow the rules, or how to handle time zones.

Under this hypothesis, midnight starts when the Mogwai’s distance from the sun has peaked for that day. If the Mogwai’s orientation on the Earth in relation to the Sun is the reason for the rule, then it’s plausible to think that the time when they can eat again is also affected by the sun.  It might be halfway between the solar noon and “midnight” (The quotes are fine–I’m being ironic. Saying I’m being ironic is fine, too, because I know what the word “ironic” means. I play fast and loose with my punctuation, especially around quotes that are used for purposes other than to indicate dialog, because I’m a wild man who does these crazy irresponsible things with commas.) which is about 6am, and sometimes it’s light out and sometimes it isn’t.  Or it might be when the Mogwai has reached solar dawn because, hey, why not?  Either way, moving very quickly to the East after midnight has passed might help feed the Mogwai earlier, and Daylight Savings Time is not a concern because you’re getting your time from an astrolabe.

Second hypothesis: photobiology is the cause for the laws. We already know that light affects their mortality–why couldn’t sunlight affect their digestion? If that’s the cause, then like medicine, the effects of light remain in the system for some time after the last exposure to light.  The rules use midnight as the earliest time in China or in Kingston Falls, NY when the sun’s radiation no longer helps the Mogwai digest food because the rules are trying to simplify things. Without that solar radiation stored in their bodies, their body mutates, possibly as a survival mechanism when food enters their system, and all hell breaks loose. With that stored radiation, Mogwai use digestive processes similar to those found in other vertebrates to digest food and no one mutates.

If this is the case, then let’s assume for the time being that the sun doesn’t set any earlier than 4pm anywhere that Mogwai have been known to live. That would mean the solar radiation causes metabolic changes that remain active for 8 hours after the sun has disappeared, keeping everyone safe. Both movies both take place around Christmas, so the sun is going to be going down fairly early at that time of year, a few days after the winter solstice, making midnight an appropriate time for them to mutate as it’s about 8 hours after the sun set. Had Gremlins taken place on June 21st in London–or even better, Aberdeen, because who hasn’t wished that more movies took place in Aberdeen?–then there would have been lots of sun and they could all eat throughout the night without and it would have been a much less interesting movie.

If that’s the case, then midnight is the earliest “latest you can feed them” time, and you have to be careful when traveling through time zones to the West when it’s dark out. In the US, DST happens at 2am, so midnight’s already happened, no worries there.

To explain how sunlight is required to avoid mutation but any light can cause pain (death?), one may assume that non-visible parts of the sun’s spectrum help in digestion (X-rays? Infrared? Gamma rays?), but intense visible light causes adverse effects. We could take this one step further and question whether or not their digestion is the cause for their mortality; direct sunlight might increase their metabolism so much that it’s instant starvation, or that their own digestive system starts to eat their vital organs in the presence of bright light, but unless I forgot something from the movies that suggests this, I think that this line of reasoning is overly complicated. (Yes, after writing approximately 1200 words about a hypothetical situation involving imaginary creatures from a movie that’s approaching its 30th anniversary, I’m calling something overly complicated.  Also, when I was trying to think of a culturally familiar place at a more extreme latitude than the continental US, I came up with London, and that is when my internal monologue voice switched to the voice of David Tennant.)

Math Trick vs Coding Trick

I have some code where I have a value x=2^n, and I wanted to see what that n was, knowing that there’s only one 1 in the binary representation, and it’s not a huge number.  I know it’s not hard, but I was wondering if there was a better way, so I looked around.  I ran into a post from someone (student?) who had to compute the same thing without branching, and that got me thinking.

I’ve now written this two times and found a few more ways, unrolled one of them by hand to see how much that helped (some, but not a whole lot), but here are the main four contenders:  the naive way, the log-trick way, inline assembly language, and using DeBruijn sequence:

Code: (all were set inside an int func(int) wrapper)

  1. while((x>>=1)>1) y++;
  2. y=log(x)/log(2);
  3. asm(“fld1; fld x; fyl2x; fstp y;”)  (wrapped with type conversions from integer to float and back)
  4. y=myDeBruijnArray[(unsigned int)(x*0x077CB531U) >> 27]; (where “myDeBruijnArray” is a lookup table 32 32-bit numbers)

Times:  (for 10,000,000 iterations)

  1. 0.602, our base case for 16 bits.  Counting 8 bits ran almost twice as fast, as one would expect, and I’d imagine that counting out 32 bits would take even longer.
  2. 2.098, which makes sense because we’re doing two function call to math libraries, but it met the condition of “no branching” that the one student had.
  3. 0.521 or 0.715 (see below), which gets us out of our conditional, but at the cost of using the FPU which has a suprising amount of overhead, and again, the number of bits makes no appreciable difference.
  4. 0.283, which has an “expensive” imul opcode, but that’s it.

One interesting thing about the assembly language:

I expected the function that was all inline assembly language and some space for variable to result in the smallest code, and it wasn’t.  There were 14 more extra assembly language operations to convert between the unsigned int value I had to start with and the floating point values I needed for the assembly language and back again.  The DeBruijn method used the standard headers and footers for the command that all of the versions used, and then four lines:

mov  eax,dword ptr [x]
imul eax, eax,77CB531h
shr eax, 1Bh
mov eax, dword ptr myDeBruijnArray [eax*4]

Because of conversion time, I wanted to try doing the inline assembly code, but instead of calling the routine with the integers I was using elsewhere, I changed from an integer to a floating point before making the call to the routine, leaving the assembly language version strictly in floating point numbers, and it turns out that using assembly language with all floating-point values saved enough time for assembly language to be a hair faster than the naive approach, and of course if I had to use floating points anyways, it’s a *lot* faster than calling the math libraries.  It turns out that I could even drop the last “store my FPU register in Y” and leave it on the top of the stack for the return value, which is what “return y” does anyways, so now that function looks like this in assembly language,

fld1
fld         dword ptr [x] 
fyl2x

They take longer to run than the op codes we needed for the DeBruijn code, but that code *only* works for integers, and knowing that there’s a log2 function in the processor that’s not in the standard library cuts my time by 75%, which if I had to do a lot of it (data mining?  Video processing?) could be very significant.  Also, use integer variables instead of floating-point variables when you do not need the latter.

Special icons

It’s common knowledge that favicon.ico will let you change the icon that most browsers use for the bookmarks, tabs, etc.

For Apple devices, you want to read this:

http://developer.apple.com/library/safari/#documentation/appleapplications/reference/safariwebcontent/configuringwebapplications/configuringwebapplications.html

To summarize:

apple-touch-icon.png for iPhones before 4.0, and they should be 57×57 pixels.

apple-touch-icon-72×72.png for iPads

apple-touch-icon-114×114.png for iPhone4

5-bit code

While in the employment of PSU, I was charged with implementing an online license system. Part of that implementation involved the user entering in data that was printed, either in a textbook or from a webpage, and at some point we were using an SHA-1 digest, which meant that this involved 160 bits, or 20 bytes, of data.

From http://en.wikipedia.org/wiki/SHA-1, we have the SHA1 hash of “The quick brown fox jumps over the lazy dog” represented as 2fd4e1c6 7a2d28fc ed849ee1 bb76e739 1b93eb12, which, as it’s using hex which uses 4 bits per digit, is 40 keystrokes.

While I didn’t really consider this option at the time, it turns out that using A-Z, a-z, 0-9, and two more characters, we could get 6-bits per keystroke for 27 characters, but that would involve a lot of confusion and hitting the Shift key a lot, which if you count as a keystroke, would bring up the keystroke count to (27*(1+(26/64))=almost 38 actual keystrokes, if you only needed the Shift key for the uppercase alphabet. That number could be decreased a little by removing some of the uppercase alphabet and using more non-alphanumeric symbols, but it also would be slightly less efficient to code and is a lot less elegant.

The solution was to use a 5-bit alphabet that was not case-sensitive. Using A-Z and 0-9 gives us 36 characters, and for a 5-bit alphabet we would only need 32 different characters. Using 5 bits per keystroke, we would also have 32 characters, a 20% improvement over the original 40. My solution was to drop the numbers 0 and 1, and the letters o and i, and to always display these codes that the user needed to enter in uppercase letters. None of these 32 characters look so similar that they would be mistyped, and they are all available on American and European keyboard layouts: 23456789ABCDEFGHJKLMNPQRSTUVWXYZ. Furthermore, two of the blocks of characters appear in the ASCII table in 3-bit blocks: 2-9 and A-H, making it easy and fast to decode using one bit test, one integer comparison, and one integer subtraction per 5-bit digit, plus whatever bit shifting would be necessary to line it up as part of a larger value.

Representing the two most significant bits by column, and the 3 least significant bits by row, we get the following, color-coded for each grouping of characters that are adjacent in both ASCII and my 5-bit encoding:

5-bit Code
msb=0 msb=1
00 01 10 11
000 2 A J S
001 3 B K T
010 4 C L U
011 5 D M V
100 6 E N W
101 7 F P X
110 8 G Q Y
111 9 H R Z

The fact that my initials are the first characters each of the letter-based columns is purely coincidental.

Example, using the previous sample data:

2fd4e1c67a 2d28fced84 9ee1bb76e7 391b93eb12 (grouped as 4 40-bit groupings)

2fd4e1c67a = 0010 1111 1101 0100 1110 0001 1100 0110 0111 1010 (grouped in 4-bits)

00101 11111 01010 01110 00011 10001 10011 11010 = 7ZCG5KMU(grouped in 5-bits)

2d28fced84 = 00101 10100 10100 01111 11001 11011 01100 00100 = 7NNHTVE6

9ee1bb76e7 = 10011 11011 10000 11011 10110 11101 10111 00111 = MVJVQXR9

391b93eb12 = 00111 00100 01101 11001 00111 11010 11000 10010 = 96FT9USL

So, instead of

2fd4e 1c67a 2d28f ced84 9ee1b b76e7 391b9 3eb12

we have

7ZCG 5KMU7NNH TVE6 MVJV QXR9 96FT 9USL

with no confusion over the “is it an 0 or an O, a 1 or an l or an I?” issue, fewer keystrokes than some other systems (hex),nearly maximized data per keystroke.

Rex Manning Day

A friend of mine and I were talking about Rex Manning Day and how she’s wants it to be a holiday, and then decided that it should be on August 5th because it sounded good.

I say that it’s in late April, probably April 22th but the 24nd or 15th are also semi-likely.

Why?  (if you HAVEN’T seen the movie from over a decade ago… spoiler alert)

My alcohol-addled brain (this conversation happened Saturday night) was telling me that they’re all wearing light jackets in the movie, and why would they be wearing jackets on August 5th in the US if they’re kinda close to Atlantic City?  But that begs the question, “so… when WAS Rex Manning Day?”

We know that Lucas closes the store, rides to Atlantic City, loses the money, and rides back by morning sometime before 9am when the store opens.  Gina’s car appears to have a Delaware license plate, which doesn’t mean much, but for sake of argument let’s go ahead and assume that Gina lives in Delaware and that the store is either in Delaware or just across the border in a neighboring state.  Wilmington, DE to Atlantic City, NJ, is a 1hr 35min drive according to MapQuest, although most of Delaware would have a longer drive.

Leaves were on the ground, presumably either just fallen from the tree, or the snow has melted, it’s spring, and they’re left-over from autumn.  State College picks up leaves from April 2nd ’till sometime in May this year, so apparently April is a good month to be picking up leaves in spring.

Corey is studying calculus and it’s assumed that she’s going to Harvard, graduating class of 1999.  Studying calculus… she’s probably a high school senior.  A.J. is accepted into art school in Boston so he can be with Corey.  That’s a HELL of an early-admissions program if he’s doing this in fall.  I see it much more likely that he applied late, which supports my “probably spring sometime” theory.

Corey’s still in school but is there at 9am.  She doesn’t seem like she’d be skipping school.  The store is also open until midnight, which makes it unlikely that the day is a Sunday.  The turnout for the big party at the end is supported a bit more by the day being a Friday or Saturday. “Warren” is also young but he seems the type to not be concerned with skipping school to go shoplifting instead, BUT no one at the store mentions that he should be in school, so perhaps that’s also in support of the Saturday Rex Manning Day theory.  And again, in the Rex Manning sign in the door of the store when Joe opens up looks like it starts with an 8, which is a lot closer to an “S” than it is to an “F”.

In the office on the whiteboard, the new releases are from May to July.  In the FRONT of the store, you might list the “new releases” as albums that were recently released, but in the OFFICE, you’d use a whiteboard for things to do, therefore, “the future”.  As there were no new releases listed for April, one would assume that the date is the end of April, which is the only reason I’m discarding the 15th as the most-likely date.

There’s a sign for Rex Manning when Joe’s opening the door to the store that lists the Where as Empire Records, the When as something too hard to read (looks like it starts with an “8”, but I think it’s probably an “S”, and the Hours as 3 to some other time that’s also too hard to read.

When Lucas is in Atlantic City, he drives by a light sign that says “April 23 8:00pm”.  BUT… it was dark in Joe’s office when they closed, it was really dark when Lucas rode into Atlantic City… I don’t think it was the current date/time.  I think it was part of the display, and if we had seen the sign for a little bit longer, then either before or after the time, we’d have seen a display that would let us know what event was going to be happening on April 23rd at 8:00pm.
If Lucas was IN Atlantic City at 8pm on April 23rd, then he would have left the office by at least 7, and it would have been pretty bright out beforehand when he was pretending to play drums on the pile of money.

So, until there’s a high definition version of this movie out, or I get ahold of the re-release with more deleted scenes that might have more information, I think that Empire Records took place on April 22nd, 1995.

Now you know.  I heard that knowing is half the battle.