Paul Graham says that compiled, tail recursive and type cast LISP code
runs faster than C code, so I'm wondering if anybody can explain to me
how you declare a variable as a certain type in clisp. The real
problem is that the following code (designed to find the first
fibonacci number with 1000 digits) gives me a floating point overflow,
which is weird because I don't see why LISP would assume I'm dealing
with floating point numbers.
(defun fib (flist)
(cond
(( = (floor (log (car flist) 10)) 999)
(cons (cadr flist) (list (car flist))))
(t (fib (cons (+ (car flist) (cadr flist)) flist)))))
Thanks in advance.
In article <························@h40g2000cwb.googlegroups.com>,
·················@gmail.com" <················@gmail.com> wrote:
> Paul Graham says that compiled, tail recursive and type cast LISP code
> runs faster than C code,
This might sometimes be the case, but it's hardly guaranteed that
type-declared Lisp code will always run faster than C code. Using type
declarations here is probably a bad idea, because Fibonacci numbers
quickly get big enough that you need to use a bignum to store them.
Certainly the element you're looking for (the first element with
more than 1000 digits) is not going to fit into a machine word.
> so I'm wondering if anybody can explain to me
> how you declare a variable as a certain type in clisp.
CLISP is an implementation of Common Lisp; "clisp" is generally
used to mean that implementation only and not Common Lisp
proper.
> The real
> problem is that the following code (designed to find the first
> fibonacci number with 1000 digits) gives me a floating point overflow,
> which is weird because I don't see why LISP would assume I'm dealing
> with floating point numbers.
> (defun fib (flist)
> (cond
> (( = (floor (log (car flist) 10)) 999)
> (cons (cadr flist) (list (car flist))))
> (t (fib (cons (+ (car flist) (cadr flist)) flist)))))
>
> Thanks in advance.
This code is pretty obscure. What about this:
(defun first-fibonacci-satisfying (test-fn)
"Loop through the Fibonacci numbers, returning the first element
that satisfies TEST-FN and the zero-based index of that element in the
sequence."
(loop for a = 1 then b
and b = 1 then (+ a b)
for index from 0
when (funcall test-fn a)
do (return (values a index))))
;; or, if you don't like LOOP
(defun first-fibonacci-satisfying (test-fn)
(do ((a 1 b)
(b 1 (+ a b))
(index 0 (1+ index)))
((funcall test-fn a) (values a index))))
(first-fibonacci-satisfying (lambda (x) (> x 5))) ;; => 8, 5
(first-fibonacci-satisfying #'evenp) ;; => 2, 2
(first-fibonacci-satisfying
(lambda (num)
(>= (length (princ-to-string num)) 1000)))
;; =>
1070066266382758936764980584457396885083683896632151665013235203375314520
6046940406218891475824897926578046948881775919574843364666725699595129960
3046126274809248218614406943305123477444275027378175308757939166619214925
9186759553966422837148943113074699503439547001985432609723067290192870526
4472437261177158218255484911205250132014786129659313817922355596574520395
0613755146783754322911960212993404826070617539770684706820289548690266618
5435124521900369480641357447470911707619766945691070098024393439617474103
7369125032313655321647736970231677550515951735184605799549194109677783732
2966579658164651390348815425631018422419025984608800011018625555024549393
7113651657039447629584714548523425950428582425306083544435428212611008992
8637950480068943303097732178348645431132057656598684562886168087186938352
9735064398629764066000072356291790520705116407761481249188583094594056668
8339109350944456576357666151619317753792891661581327159616877487983821820
492520348473874384736771934512787029218636250627816, 4781
Although you probably don't want type declarations here (as explained
above), here is how you write optimized Lisp code:
(defun add-numbers (a b c)
;; unoptimized version
(+ a b c))
(with-output-to-string (*standard-output*)
(disassemble 'add-numbers))
"200C4002:
0: 80FD03 cmpb ch, 3
3: 7535 jne L2
5: 3B25EC330020 cmp esp, [200033EC] ;
SYSTEM:*%STACK-LIMIT
11: 762D jbe L2
13: 55 push ebp
14: 89E5 move ebp, esp
16: 50 push eax
17: 8B5D0C move ebx, [ebp+C]
20: 0B5D08 or ebx, [ebp+8]
23: F6C303 testb bl, 3
26: 7532 jne L4
28: 8B7D0C move edi, [ebp+C]
31: 037D08 add edi, [ebp+8]
34: 702A jo L4
L1: 36: 89FB move ebx, edi
38: 0B5DFC or ebx, [ebp-4]
41: F6C303 testb bl, 3
44: 7511 jne L3
46: 89F8 move eax, edi
48: 0345FC add eax, [ebp-4]
51: 700A jo L3
53: FD std
54: C9 leave
55: C20800 ret 8
L2: 58: E841D40400 call 20111482 ; #<Function
RUNTIME:BAD-ARGS-OR-STACK 20111482>
L3: 63: 897D0C move [ebp+C], edi
66: 8B45FC move eax, [ebp-4]
69: C9 leave
70: 8F0424 pop [esp]
73: E9AABF0400 jmp 2010FFFA ; #<Function
SYSTEM::*%+$ANY-STUB 2010FFFA>
L4: 78: FF750C push [ebp+C]
81: 8B4508 move eax, [ebp+8]
84: E89FBF0400 call 2010FFFA ; #<Function
SYSTEM::*%+$ANY-STUB 2010FFFA>
89: 89C7 move edi, eax
91: EBC7 jmp L1
93: 90 nop
"
(defun add-numbers-optimized (a b c)
;; optimized version
(declare (optimize (speed 3) (safety 0) (debug 0)))
(declare (type fixnum a b c))
(the fixnum (+ a b c)))
(with-output-to-string (*standard-output*)
(disassemble 'add-numbers-optimized))
"200F796A:
0: 55 push ebp
1: 89E5 move ebp, esp
3: 50 push eax
4: 8B5D0C move ebx, [ebp+C]
7: 8B7D08 move edi, [ebp+8]
10: 53 push ebx
11: B502 moveb ch, 2
13: 89F8 move eax, edi
15: FF156CF81B20 call [201BF86C] ; SYSTEM:+$FIXNUM
21: 89C3 move ebx, eax
23: 0B5DFC or ebx, [ebp-4]
26: F6C303 testb bl, 3
29: 750E jne L1
31: 89C7 move edi, eax
33: 037DFC add edi, [ebp-4]
36: 7007 jo L1
38: FD std
39: 89F8 move eax, edi
41: C9 leave
42: C20800 ret 8
L1: 45: 89450C move [ebp+C], eax
48: 8B45FC move eax, [ebp-4]
51: C9 leave
52: 8F0424 pop [esp]
55: E954860100 jmp 2010FFFA ; #<Function
SYSTEM::*%+$ANY-STUB 2010FFFA>
60: 90 nop
61: 90 nop
"
The optimized, type-declared code will save a lot of assembly
instructions and a lot of potentially expensive calls, but there is a
price: the code is significantly uglier, you no longer get
automatic bignums (i.e. integers can overflow, just like C), and +
no longer checks its arguments to make sure they're actually numbers.
In short, you should only optimize where absolutely necessary
(i.e. where profiling indicates a bottleneck), and focus instead on
making higher-level improvements to your algorithms and data structures.
HTH,
Bill
·················@gmail.com" <················@gmail.com> writes:
> Paul Graham says that compiled, tail recursive and type cast LISP code
> runs faster than C code, so I'm wondering if anybody can explain to me
> how you declare a variable as a certain type in clisp. The real
> problem is that the following code (designed to find the first
> fibonacci number with 1000 digits) gives me a floating point overflow,
> which is weird because I don't see why LISP would assume I'm dealing
> with floating point numbers.
> (defun fib (flist)
> (cond
> (( = (floor (log (car flist) 10)) 999)
> (cons (cadr flist) (list (car flist))))
> (t (fib (cons (+ (car flist) (cadr flist)) flist)))))
The overflow is coming from (log (car flist) 10). Log is
converting its argument to a floating point number with a
view to using a polynomial approximation to compute the
logarithm, but doesn't get that far.
Alan Crowe
Edinburgh
Scotland
·················@gmail.com" <················@gmail.com> writes:
> Paul Graham says that compiled, tail recursive and type cast LISP code
> runs faster than C code, so I'm wondering if anybody can explain to me
> how you declare a variable as a certain type in clisp. The real
> problem is that the following code (designed to find the first
> fibonacci number with 1000 digits) gives me a floating point overflow,
> which is weird because I don't see why LISP would assume I'm dealing
> with floating point numbers.
> (defun fib (flist)
> (cond
> (( = (floor (log (car flist) 10)) 999)
> (cons (cadr flist) (list (car flist))))
> (t (fib (cons (+ (car flist) (cadr flist)) flist)))))
Implementations are allowed to use floating point numbers to compute
LOG, even if the input is an integer.
So, when the argument is an integer too big to be coerced to a
floating point, this function may complain, even if the result would
be integer or stand in a floating point value.
You could use:
(= (integer-length (car flist)) 3318)
--
__Pascal Bourguignon__ http://www.informatimago.com/
Grace personified,
I leap into the window.
I meant to do that.
Thanks to everyone for responding. I feel dumb for not catching the
log problem, but I was only computing logs of integers and I didn't
care about how precise the values were. I replaced the code with
(( = (floor (/ (car flist) (expo 10 998))) 1) which does the same
thing more efficiently. As for type casting, can anybody tell me all
the types in LISP, how much typecasting will actually optimize code,
and how typecasting alters the compilation process (I realize this is a
tall order but would appreciate any answers at all).
In article <························@i15g2000cwa.googlegroups.com>,
·················@gmail.com" <················@gmail.com> wrote:
> Thanks to everyone for responding. I feel dumb for not catching the
> log problem, but I was only computing logs of integers and I didn't
> care about how precise the values were. I replaced the code with
> (( = (floor (/ (car flist) (expo 10 998))) 1) which does the same
> thing more efficiently. As for type casting, can anybody tell me all
> the types in LISP, how much typecasting will actually optimize code,
> and how typecasting alters the compilation process (I realize this is a
> tall order but would appreciate any answers at all).
Listing all of the types in Lisp is a tall order indeed, since all
of the following are types:
(integer 0 200) ;; an integer greater than 0 and less than 200
(integer -1 3000) ;; etc, etc.
(or integer float)
(or string symbol (satisfies my-custom-object-p))
Lisp objects can be members of quite a few types:
CL-USER 4 > (typep 3 '(integer 0 1000))
T
CL-USER 5 > (typep 3 '(integer -1 1000))
T
CL-USER 6 > (typep 3 'rational)
T
CL-USER 7 > (typep 3 '(member 1 2 3))
T
CL-USER 8 > (typep 3 '(satisfies oddp))
T
When it comes to optimizing code for efficiency, you are probably
going to be concerned with only a few types, like FIXNUM (almost always
an integer that can fit in a machine word), SINGLE-FLOAT, and
DOUBLE-FLOAT.
Declaring types often involves trial and error, and your code loses
a lot of readability when you decide to do so. There is a good
description of optimization in the last chapter of Peter Seibel's book:
http://www.gigamonkeys.com/book
Only certain type declarations will actually have an effect on
efficiency. For example, this code:
(let ((x 2))
(declare (optimize (speed 3) (debug 0) (safety 0))
(declare (type fixnum x))
(the fixnum (* x 2)))
will probably compile to very efficient machine code, because the
compiler can assume that X will never hold a number bigger than
what fits in a machine word (technically, the standard doesn't specify
that a FIXNUM must fit in a machine word, but this is almost always
the case) and can use the CPU's ADD instruction.
On the other hand, replacing FIXNUM with INTEGER in the THE form and
the type declaration won't help you much, because the compiler
can't make very many optimizations with such a vague declaration (an
integer has to be able to transform into a bignum, which precludes
representing X as a machine word and using the CPU's arithmetic
instructions to manipulate it).
Type declaration should be a last resort, and should only be done in
parts of your code that a profiler has singled out as wasteful - if it
ain't broke, don't fix it.