"I have a mind like a steel... uh... thingy." Patrick Logan's weblog.

Search This Blog

Loading...

Tuesday, June 06, 2006

Integers

Tim Bray wonders about Java and binary search...

If we can’t get binary search right, what chance do we have with real software?
Psst... look at the code. You *did* get binary search right.

The problem is you got integers wrong.

Real programmers use the *complete* numeric tower.

Update: Troy makes a point in the comments that there are many basic algorithms that are easy to get wrong when the foundation is weak.

Without having to think about integer overlow you are free to think more mathematically and less mechanically. Here is an unusual (to most) definition of factorial. This is iterative using the "let-loop" syntax which can be added trivially to Scheme since it has lambda and tail recursion. OK -- C# and Java have a new iteration syntax the compiler writers added for you. Can you iterate on multiple parameters? Can you invoke the next iteration even in a non-tail-recursive position?

Ha! We *still* win! But you still have more programmers.

But we still have the complete numerical tower!!! Yea!

> (define (fact n)
    (if (< n 0) (error "fact n, n >= 0")
        (if (< n 2)
            1
            (let loop ((result n) (n (- n 1)))
               (if (< n 2)
                   result
                   (loop (* result n) (- n 1)))))))
> (fact -1)
*** ERROR IN (console)@52.1 -- fact n, n >= 0
1> ,t
> (fact 0)
1
> (fact 2)
2
> (fact 6)
720
> (fact 100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
> (time (fact 1000))
(time (fact 1000))
    25 ms real time
    30 ms cpu time (30 user, 0 system)
    8 collections accounting for 3 ms real time (0 user, 0 system)
    1230816 bytes allocated
    no minor faults
    no major faults
40238726007709377354370243392300398571937486421071463254379991042993851239862902059204420848696940480047998861019719605863166687299480855890132382966994459099742450408707375991882362772718873251977950595099527612087497546249704360141827809464649629105639388743788648733711918104582578364784997701247663288983595573543251318532395846307555740911426241747434934755342864657661166779739666882029120737914385371958824980812686783837455973174613608537953452422158659320192809087829730843139284440328123155861103697680135730421616874760967587134831202547858932076716913244842623613141250878020800026168315102734182797770478463586817016436502415369139828126481021309276124489635992870511496497541990934222156683257208082133318611681155361583654698404670897560290095053761647584772842188967964624494516076535340819890138544248798495995331910172335555660213945039973628075013783761530712776192684903435262520001588853514733161170210396817592151090778801939317811419454525722386554146106289218796022383897147608850627686296714667469756291123408243920816015378088989396451826324367161676217916890977991190375403127462228998800519544441428201218736174599264295658174662830295557029902432415318161721046583203678690611726015878352075151628422554026517048330422614397428693306169089796848259012545832716822645806652676995865268227280707578139185817888965220816434834482599326604336766017699961283186078838615027946595513115655203609398818061213855860030143569452722420634463179746059468257310379008402443243846565724501440282188525247093519062092902313649327349756551395872055965422874977401141334696271542284586237738753823048386568897646192738381490014076731044664025989949022222176590433990188601856652648506179970235619389701786004081188972991831102117122984590164192106888438712185564612496079872290851929681937238864261483965738229112312502418664935314397013742853192664987... 
(goes on for several more lines)

2 comments:

Troy said...

This is the same sort of limitation that leads to factorial implementations only working for 27! or some such artificial appearing upper bound. I can still remember college teachers botching the explanation of why this happened.

jto said...

"let loop" is actually built-in in R5RS.

Blog Archive

About Me

Portland, Oregon, United States
I'm usually writing from my favorite location on the planet, the pacific northwest of the u.s. I write for myself only and unless otherwise specified my posts here should not be taken as representing an official position of my employer. Contact me at my gee mail account, username patrickdlogan.