Programs from the past, Part III: It's a numbers game

* * * * *

Programs from the past, Part III: It's a numbers game

I'm still not done yet. When last we left off [1], the recreation of a
project written twenty-some years ago [2] wasn't as fast as I thought. But as
I shall reveal, there's a bit more lurking here than I realized.

For a fair comparison, I actually have two versions of a program that
generates those map files:

[Yeah, this again] [3]

One version in C and one in Lua [4] (previously, the recreated programs just
spit out numbers that were then converted to an image with a second program).
And here's how long it took to generate the results:

Table: Timings to generate a map file
Version Timings
------------------------------
Original program ~36,000s
Lua 1,096s
C 79s
LuaJIT [5] 69s

(remember, the “Original program” was written twenty-some years ago and ran
on a 32-bit 33MHz (megaHertz) machine; the programs I just wrote are running
on a 64-bit 2.8GHz (gigaHertz) machine)

My initial mistake in recreating this program was to toss out values that
exceeded a range and from that, I got fantastic timings, but I was throwing
out too much, as can be seen here:

[Trimming things a bit too close] [6]

The “too-trimmed” version came about because I looked at some of the
intermediate results and saw infinities (well, the IEEE (Institute of
Electrical and Electronics Engineers) 754 [7]'s concept of infinity) and at
that point, any operations done on “infinity” is “infinity.”

But my mistake was thinking that all values that fell out of range would end
up being “infinite.” Not all did, and some even fell back into range.

But I was still troubled by the infinite results. So, why not explicitely
check for “infinity?” In Lua/LuaJIT:

> if xn == math.huge or xn == -math.huge then return MAX end
> if yn == math.huge or yn == -math.huge then return MAX end
>

And in C:

> if (xn == HUGE_VAL) return MAX;
> if (xn == -HUGE_VAL) return MAX;
> if (yn == HUGE_VAL) return MAX;
> if (yn == -HUGE_VAL) return MAx;
>

(for those curious, HUGE_VAL is defined in math.h.)

Adding those lines makes all the difference:

Table: Updated timings to generate a map file
Version Timings
------------------------------
Original program N/A (Not Applicable)
Lua 16.25s
C 2.60s
LuaJIT 1.25s

It's nice to see LuaJIT still beating the snot out of C, and yes, I was able
to generate a full set of maps, just like I did twenty-some years ago, in
under three minutes (remember, I'm running the code across four CPU (Central
Processing Unit)s).

But now I'm upset, because checking for “infinity” was something I didn't do
twenty-some years ago, and now I'm thinking, what if I had? Could that simple
check, had I known about it, cut the run time of a year down to a month?

I can't blame the university for not offering a class on floating point
arithmetic, because it did! And worse, I took the class! (when I entered FAU
(Florida Atlantic University) [8] as a freshman, I knew that the first class
for the Computer Science degree involved Fortran [9]. I found the first class
that had “Fortran” as part of the title and signed up for it, only to spend
find the lectures spending more time on the horrors of floating point
arithmetic [10] and very little time on programming. It turned out I took the
wrong class; what I signed up for was a Fortran class taught out of the Math
Department (the very one I worked for when I wrote these programs twenty-some
years ago) for mathematicians. When I discovered the mistake, I was able to
get out of the class without issue, but only becuase I was actually doing
quite well. In my defense, I was a freshman and didn't have my act together;
but FAU (Florida Atlantic University) didn't exactly have a Computer Science
Department at the time, so it didn't have its act together either!). It never
dawned on me to even check the intermediate results and bail early.

Sigh.

[1] gopher://gopher.conman.org/0Phlog:2013/08/05.1
[2] gopher://gopher.conman.org/0Phlog:2013/08/04.1
[3] https://boston.conman.org/2013/08/05/map.png
[4] http://www.lua.org/
[5] http://luajit.org/
[6] https://boston.conman.org/2013/08/04/map1.png
[7] https://en.wikipedia.org/wiki/IEEE_floating_point
[8] http://www.fau.edu/
[9] http://en.wikipedia.org/wiki/Fortran
[10] http://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html

Email author at [email protected]