[PLUG-TALK] Autodialer numerical math puzzle

[Russell Senior]

>>>>> "Keith" == Keith Lofstrom <keithl at kl-ic.com> writes:

Keith> Math puzzle:

Keith> John Jones sets up a program to use his nifty new computer
Keith> autodialer.  He sets the program up to call "911".
Keith> Unfortunately, he hits the shift key and enters 9!! instead.
Keith> That is, (9 factorial)factorial.

Keith> His autodialer contains a powerful computer capable of very
Keith> high precision integer math, and it proceeds to compute this
Keith> long integer, and dial it.  John has a regular telephone on the
Keith> US public telephone network.  His autodialer dials 3 digits a
Keith> second.  He pays 3 cents per minute for long distance charges,
Keith> rounded up to the nearest cent.

Keith> Question one: What person or company does he end up calling,
Keith> with the first usable digits?  Name and address, please, as of
Keith> June 2006.

Keith> Question two: How long (in seconds) will the autodialer dial?
Keith> Ignoring taxes, how much will the phone service cost John, if
Keith> he (and the recipient) allows the whole sequence of digits to
Keith> complete?

Keith> Keith

Keith> (yes, it IS a waste of time)

This is one of the problems that is is so fun to use Lisp for.  I used
CLISP, a byte-code interpretted implementation.  The naive
implementation of factorial tends to blow the stack and/or the normal
floating point representations, or scroll the interesting bits off the
top of the screen.  So, we get slightly clever and do the math on
log-transformed values and use an iteration instead of recursion:

  > (defun factorial (n) 
      (exp (loop for i from 1 upto n 
              sum (log (coerce i 'long-float)))))

  > (factorial 9)
    => 362879.99999999999991L0
  > (time (factorial 362880))
  Real time: 48.807139 sec.
  Run time: 48.763047 sec.
  Space: 1144749160 Bytes
  GC: 1697, GC time: 20.813321 sec.
   =>1.6097144004283187662L1859933

A long-float in CLISP is a 10-byte float with 64-bits of mantissa by
default, but it is configurable at runtime, which is pretty cool.  So,
just to make sure that precision didn't mess me up, i'll try bumping
it.

  > (long-float-digits) 
  64
  > (setf (long-float-digits) 128)
  128
  > (long-float-digits) 
  128
  > (time (factorial 362880))
  Real time: 74.233911 sec.
  Run time: 74.044627 sec.
  Space: 1707733928 Bytes
  GC: 2532, GC time: 30.81393 sec.
  1.60971440041001262110344361073509278104L1859933

So, that looks stable enough to give the same first 10 digits.  BTW,
(long-float-digits) tells you how many bits (not decimal digits!) in
the float representation's mantissa.  And note how Common Lisp
magically pushes a value into a function call using 'setf.  Too cool.

Answer 1: the number is 1-609-714-4004.  Google doesn't tell me who
that is, so I give up.  Intelius says it is an "available number" in
MEDFORD, NJ. 

Answer 2: from the exponent on the resulting value, the number would
have 1859934 digits.  At three digits a second, that's 619978 seconds,
which is 30,998.9 minutes (a little over a week: 7 days, 4 hours, 12
minutes and 58 seconds).  Let's say the phone company charges in full
minutes, that's 30,999 minutes, times $0.03 = $929.97.

Note the run-time on these calculations: ~49 and ~74 seconds,
respectively, (on a 1GHz P3) so it didn't waste *that* much time.  

I wasn't willing to waste enough time to confirm I got the right
number.  I just trust that the underlying implementation of log and
exp are good enough.

For kicks, here's the output when I bump the long-float-digits to 640
(ten times normal).  

  > (setf (long-float-digits) 640)
  640
  > (time (factorial 362880))
  Real time: 408.273091 sec.
  Run time: 407.269453 sec.
  Space: 8283795960 Bytes
  GC: 12283, GC time: 129.568113 sec.
  1.609714400410012621103443610733317726505520397622886158329835221246398515391430218331773756126649701931616812922151308253312687565407611350763177052692072075380992663287299539692920504232785533L1859933

How'd I do?  Do I win anything?


-- 
Russell Senior         ``I have nine fingers; you have ten.''
seniorr at aracnet.com