REAL WORLD SCHEME DETECTED

http://nand.net/~demaria/comphum.html

million.txt - Ever wonder what 2^1000000 equals? Thanks to the power of scheme, you can see what this absurdly big number equals (warning, its^(sic) approximately 300,000 digits long and thus makes this a rather large text file of 300K).

The problem is simple enough if you imagine the number in base 2, you don't even need a computer for this.

SBCL also handles this rather fast:

CL-USER> (time (expt 2 1000000))
Evaluation took:
  0.000 seconds of real time
  0.000000 seconds of total run time (0.000000 user, 0.000000 system)
  100.00% CPU
  954 processor cycles
  0 bytes consed
 
9900656...(omitted due to size)
While I haven't checked why this is so, I believe it might be because (expt constant constant) gets inlined by the compiler... Upon checked (seconds later) with a disassembler, it seems I was right, the number is indeed inlined at compile-time, and compile-time itself was very fast - this is probably not very surprising because 2**x is just a bignum shift (as optimized by the compiler), and the only time-consuming part would be printing the number in base 10 (as opposed to its internal byte representation).


CL-USER> (lambda () (expt 2 1000000))
; disassembly for (LAMBDA ())
; 23EBBD56:       8B1528BDEB23     MOV EDX, [#x23EBBD28]      ; 9900656229295898250697923616...(omitted due to size)
;       5C:       8BE5             MOV ESP, EBP
;       5E:       F8               CLC
;       5F:       5D               POP EBP
;       60:       C3               RET
The actual partitioning of the runtime vs compile-time costs:

CL-USER> (time (compile nil '(lambda () (expt 2 1000000))))
Evaluation took:
  0.000 seconds of real time
  0.000000 seconds of total run time (0.000000 user, 0.000000 system)
  100.00% CPU
  1 lambda converted
  4,308,273 processor cycles
  282,400 bytes consed
 
#<FUNCTION (LAMBDA ()) {248A0695}>
NIL
NIL

CL-USER> (time (progn (funcall #<FUNCTION (LAMBDA ()) {248A0695}>) nil))
Evaluation took:
  0.000 seconds of real time
  0.000000 seconds of total run time (0.000000 user, 0.000000 system)
  100.00% CPU
  1,305 processor cycles
  0 bytes consed
As you can see, the cost of actually generating the code (and included bignum) and returning it are small as expected. What about the cost of printing it to base 10?


CL-USER> (time (print (funcall #<FUNCTION (LAMBDA ()) {248A0695}>) (make-broadcast-stream)))

Evaluation took:
  6.359 seconds of real time
  6.359375 seconds of total run time (6.359375 user, 0.000000 system)
  100.00% CPU
  15,285,317,868 processor cycles
  6,585,920 bytes consed
 
990065622929589825069792361630190325073362424178...
Obviously a bit more costly. Emacs itself also takes a bit to display the number as it is being sent through SLIME.