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)