Reputation: 529
If I try to evaluate the expression (expt 123456 123456)
in both Chicken Scheme (with the numbers extension) and Clisp it takes quite a long time (more in Clisp).
So I thought that evaluating the expression (/ (expt 123456 123456) (expt 123456 123456))
would take at least double that time, because the interpreter has to evaluate twice the power function and then has to evaluate a division.
But, surprisingly, the answer in both interpreters comes out almost instantaneously. What is going on? How can it be possible? Exactly, how is this expression evaluated?
Upvotes: 1
Views: 856
Reputation: 48745
In Common Lisp you have the time
macro:
(time (progn (expt 123456 123456) 1))
; Real time: 0.578002 sec.
; Run time: 0.577577 sec.
; Space: 733816 Bytes
; GC: 1, GC time: 0.007143 sec.
; ==> 1
(time (progn (princ (expt 123456 123456)) 1))
; a whole lot of numbers ...6
; Real time: 59.980278 sec.
; Run time: 59.017193 sec.
; Space: 8490376 Bytes
; GC: 4, GC time: 0.033218 sec.
; ==> 1
The differemnces between these are the producing of the the numbers in a human readable and decimal manner and getting it out on the slow console.
The second should use about double the time of the first expression:
(time (/ (expt 123456 123456) (expt 123456 123456)))
; Real time: 1.120879 sec.
; Run time: 1.11894 sec.
; Space: 1728656 Bytes
1
Indeed it does.. How about just printing the result of the first expression:
(let ((value (time (expt 123456 123456))))
(time (princ value))
1)
; Real time: 0.584907 sec. (pretty much the same time calculating the result)
; Run time: 0.584398 sec.
; Space: 733816 Bytes
; GC: 1, GC time: 0.020312 sec.
; lots of digits ...56
; Real time: 59.803486 sec. about the same time it took printing it last time
; Run time: 58.414997 sec.
; Space: 2514768 Bytes
; GC: 1, GC time: 0.002712 sec.
; ==> 1
I don't think I need to repeat this in Scheme. Console is slow, arithmetic in CL and Scheme is fast, even with bignums.
EDIT
I actually did make a script and redirected it to a file and it took around the same amount of time. Thus most of the time is used to convert the bignum into human readable chars and not actually getting it out on the console. If it was the console redirecting it to a file would drastically speed up the whole process.
Upvotes: 9
Reputation: 27424
If you try to define:
(defun f()
(expt 123456 123456))
in SBCL and CCL and then do (disassemble #'f)
you will find that the value (expt 123456 123456)
is precomputed at compile time and returned by the function. But if you define :
(defun f()
(/ (expt 123456 123456) (expt 123456 123456))
and disassemble this function, you will discover that the compiler is smart enough to compile the function such that it returns immediately the value 1.
So, you should take into account in your timings the optimizations performed by the compiler, and of course the printing of very large numbers takes up a lot of time.
Upvotes: 6
Reputation: 139251
CL-USER 2 > (time (progn (/ (expt 123456 123456) (expt 123456 123456))
(values)))
Timing the evaluation of (PROGN (/ (EXPT 123456 123456) (EXPT 123456 123456))
(VALUES))
User time = 2.861
System time = 0.009
Elapsed time = 2.858
Allocation = 8718224 bytes
228 Page faults
CL-USER 3 > (time (progn (expt 123456 123456)
(values)))
Timing the evaluation of (PROGN (EXPT 123456 123456)
(VALUES))
User time = 1.426
System time = 0.003
Elapsed time = 1.419
Allocation = 3398840 bytes
138 Page faults
Upvotes: 2
Reputation: 17876
Raising to a power is a relatively quick operation, even using big integers (it takes logarithmic time, excluding the cost of big integer arithmetic). But printing a number is a relatively slow operation (it takes quadratic time). So in your first problem printing the result takes a long time. In your second problem the result is 1, so the time is spent making the calculation, which is fast. On my computer, the first problem takes a little bit less than 2 seconds, then spends several seconds printing the result, and the second problem takes a little bit less than double that, then immediately prints 1.
Upvotes: 7