million.txt - Ever wonder what 21000000 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?
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.
% cat anus.hs
main = print $ 2 ^ 1000000
% ghc --make anus.hs
[1 of 1] Compiling Main ( anus.hs, anus.o )
Linking anus ...
% time ./anus > anus.txt
./anus > anus.txt 0.32s user 0.01s system 99% cpu 0.335 total
Really now... in ruby I get 16.108s, and part of that is spent writing to the hard drive (I had it written to a file, not printed to the screen). Your processor must suck.
>>20
Each multiplication adds about 5.5 digits on average (you'd think it's more like 3, but note that there are 9 times more 6-digit numbers in the 1M range than all other combined).
So somewhere between 5 and 6 millions decimal digits.
>>29
That wasn't my scouter. But you can still grab it.
Name:
Anonymous2010-11-17 17:56
You can do that in VB.NET too. Just write a class that re-implements the basic math operators with string-representations of numbers. Then calculate 2^1000000. You can even create the numbers with a factory, so that if the number can fit within 32 bits, only a regular number is created.
<>
Name:
Anonymous2010-11-17 19:18
Prelude> let a = 2^1000000
(0.02 secs, 4284884 bytes)
Prelude> a
<a lot of numbers>
(2.94 secs, 440502500 bytes)