I am starting to learn Common Lisp with SLIME and "Practical Common
Lisp" ...
Now, I am trying to solve this question from http://projecteuler.net/.
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
This is my answer.
(defun find-largest-prime-factor
(number)
(do ((i 2 (1+
i)))
((> i (/ number
2)))
;; if number is divisible by i
(if ((lambda (x y) (if(zerop (rem x y))T)) number
i)
;;Then try whether (number/i) is a prime and return
if it is
(if ((lambda
(z)
(loop for fac from 2 to (isqrt
z)
never (zerop (mod z fac)))) (/ number
i))
(return (/ number i))))))
Then when I ran from SLIME ...
CL-USER> (load "/media/Suboo/Programming/lisp/find-largest-prime-
factor.cl")
; Loading #p"/media/Suboo/Programming/lisp/find-largest-prime-
factor.cl".
T
CL-USER> (find-largest-prime-factor
13195)
29
CL-USER> (find-largest-prime-factor
60085147514)
10976461
CL-USER> (find-largest-prime-factor
600851475143)
Here it hangs for a long time
I waited around 5 minutes, still it doesn't print anything ..
Why it is not working for the last one ?
Is it because the number too large ?
I am using SLIME with CMUCL ...
Plz, help me ... I spend more than 2 hours to get that answer and now
it is not working ;(
·············@gmail.com writes:
> I am starting to learn Common Lisp with SLIME and "Practical Common
> Lisp" ...
Good choice.
> Now, I am trying to solve this question from http://projecteuler.net/.
>
> The prime factors of 13195 are 5, 7, 13 and 29.
> What is the largest prime factor of the number 600851475143 ?
>
> This is my answer.
>
> (defun find-largest-prime-factor
> (number)
> (do ((i 2 (1+
> i)))
> ((> i (/ number
> 2)))
> ;; if number is divisible by i
> (if ((lambda (x y) (if(zerop (rem x y))T)) number
> i)
> ;;Then try whether (number/i) is a prime and return
> if it is
> (if ((lambda
> (z)
> (loop for fac from 2 to (isqrt
> z)
> never (zerop (mod z fac)))) (/ number
> i))
> (return (/ number i))))))
A few notes:
* You are over-using lambda: E.g. instead of
((lambda (x y) (if (true-or-not x y) t)) x y)
you could just have written
(true-or-not x y)
with the same result. Are you trying to translate some obscure
lambda-calculus function into common lisp?
* Try breaking the problem down in smaller pieces: When you need to find
the biggest prime factor, you may want write a function `primep' which
test if a number is prime. Then you can use that to write your
main function.
* Avoid futile computations: when do you need to check for a
prime-number/divisibility? Can you rule out certain cases, so you
don't have to check those? (Hint: How many even prime numbers exist
in the set of natural numbers?)
* Check the way how and when functions and the do construct return a
value: The current code returns a wrong result when the input number
is prime.
> I waited around 5 minutes, still it doesn't print anything ..
> Why it is not working for the last one ?
> Is it because the number too large ?
Depends: To large for what? The lisp system? The algorithm? Your
patience?
HTH
A
> * You are over-using lambda: E.g. instead of
> ((lambda (x y) (if (true-or-not x y) t)) x y)
> you could just have written
> (true-or-not x y)
> with the same result. Are you trying to translate some obscure
> lambda-calculus function into common lisp?
No, it is just I wanna practice more about lambda as it is the most
troubling one for me to understand ...
> * Try breaking the problem down in smaller pieces: When you need to find
> the biggest prime factor, you may want write a function `primep' which
> test if a number is prime. Then you can use that to write your
> main function.
Yeah, I already tried the same with (defun primep ....
It is the same result ...
> * Avoid futile computations: when do you need to check for a
> prime-number/divisibility? Can you rule out certain cases, so you
> don't have to check those? (Hint: How many even prime numbers exist
> in the set of natural numbers?)
Thanks, that is a good hint ...
> * Check the way how and when functions and the do construct return a
> value: The current code returns a wrong result when the input number
> is prime.
Yeah, I am gonna try again !
> > I waited around 5 minutes, still it doesn't print anything ..
> > Why it is not working for the last one ?
> > Is it because the number too large ?
> Depends: To large for what? The lisp system? The algorithm? Your
> patience?
I am sure it is not my patience ....
Because, (find-largest-prime-factor 60085147514) for this one, it
just takes a fraction of a second to calculate ...
But for this one, (find-largest-prime-factor 600851475143) I waited
more than 5 minutes ...
I am gonna find out what's wrong ....
Thanks for your help and advices, brother ;)
·············@gmail.com wrote:
>>* You are over-using lambda: E.g. instead of
>> ((lambda (x y) (if (true-or-not x y) t)) x y)
>> you could just have written
>> (true-or-not x y)
>> with the same result. Are you trying to translate some obscure
>> lambda-calculus function into common lisp?
>
>
> No, it is just I wanna practice more about lambda as it is the most
> troubling one for me to understand ...
Sure! I had trouble learning to ride a bicycle so I would always lie on
my back on my desk bicycling in the air. Got in a lot of trouble with
the teacher. And swimming was tough. I would hang out the window of the
car swimming with my arms. I can tell you from experience, watch out for
crossing guards. But my French does not seem to get better no matter how
much time I spend down in the barrio...
kxo
!
·············@gmail.com napisa�(a):
> I am sure it is not my patience ....
> Because, (find-largest-prime-factor 60085147514) for this one, it
> just takes a fraction of a second to calculate ...
> But for this one, (find-largest-prime-factor 600851475143) I waited
> more than 5 minutes ...
> I am gonna find out what's wrong ....
What are smallest factors ?
--
A
.
On 2008-12-04, Albert Krewinkel <·········@gmx.net> wrote:
> * You are over-using lambda: E.g. instead of
> ((lambda (x y) (if (true-or-not x y) t)) x y)
No way!
((lambda (fx fy) (if (true-or-not (funcall fx) (funcall fy)) t))
(lambda () x) (lambda () y))
:)
On Dec 4, 12:14 pm, Albert Krewinkel <·········@gmx.net> wrote:
> ·············@gmail.com writes:
> > I am starting to learn Common Lisp with SLIME and "Practical Common
> > Lisp" ...
>
> Good choice.
>
>
>
> > Now, I am trying to solve this question fromhttp://projecteuler.net/.
>
> > The prime factors of 13195 are 5, 7, 13 and 29.
> > What is the largest prime factor of the number 600851475143 ?
>
> > This is my answer.
>
> > (defun find-largest-prime-factor
> > (number)
> > (do ((i 2 (1+
> > i)))
> > ((> i (/ number
> > 2)))
> > ;; if number is divisible by i
> > (if ((lambda (x y) (if(zerop (rem x y))T)) number
> > i)
> > ;;Then try whether (number/i) is a prime and return
> > if it is
> > (if ((lambda
> > (z)
> > (loop for fac from 2 to (isqrt
> > z)
> > never (zerop (mod z fac)))) (/ number
> > i))
> > (return (/ number i))))))
>
> A few notes:
>
> * You are over-using lambda: E.g. instead of
> ((lambda (x y) (if (true-or-not x y) t)) x y)
> you could just have written
> (true-or-not x y)
> with the same result. Are you trying to translate some obscure
> lambda-calculus function into common lisp?
>
> * Try breaking the problem down in smaller pieces: When you need to find
> the biggest prime factor, you may want write a function `primep' which
> test if a number is prime. Then you can use that to write your
> main function.
>
> * Avoid futile computations: when do you need to check for a
> prime-number/divisibility? Can you rule out certain cases, so you
> don't have to check those? (Hint: How many even prime numbers exist
> in the set of natural numbers?)
>
> * Check the way how and when functions and the do construct return a
> value: The current code returns a wrong result when the input number
> is prime.
>
> > I waited around 5 minutes, still it doesn't print anything ..
> > Why it is not working for the last one ?
> > Is it because the number too large ?
>
> Depends: To large for what? The lisp system? The algorithm? Your
> patience?
>
> HTH
> A
Division is expensive, probably even more for bignums. Try to reduce
them. When generating prime factors, as soon as you find a prime,
divide the input value by that factor and use the result for further
calculations.
(defun enum-prime-factors (n)
(let ((factors nil) (p 2))
(loop while (> n 1) do
(if (zerop (mod n p))
(progn
(if (or (eq factors nil) (/= (caar factors)
p))
(setf factors (cons (list p 1) factors))
(incf (cadar factors)))
(setf n (/ n p)))
(incf
p)))
(reverse factors)))
CL-USER> (time (enum-prime-factors 600851475143))
Evaluation
took:
0.002 seconds of real
time
0.001216 seconds of user run
time
0.0 seconds of system run
time
0 calls to
%EVAL
0 page faults
and
24,576 bytes
consed.
((71 1) (839 1) (1471 1) (6857 1))
2GHz Core 2 Duo
I rewrote this without a loop, and posted it somewhere, but I can't
find it right now.
Regards
Gautham
> 2GHz Core 2 Duo
>
> I rewrote this without a loop, and posted it somewhere, but I can't
> find it right now.
>
> Regards
> Gautham
Here it is. Seems to be faster, although I am not sure why. Any ideas?
(defun factor-primes (n)
(labels
((factor-primes-2 (n f)
(if (<= n 1)
nil
(if (zerop (mod n f))
(cons f (factor-primes-2 (/ n f) f))
took:
(factor-primes-2 n (1+ f))))))
(cons 1 (factor-primes-2 n 2))))
Regards
Gautham
> 2GHz Core 2 Duo
>
> I rewrote this without a loop, and posted it somewhere, but I can't
> find it right now.
>
> Regards
> Gautham
Here it is. Seems to be faster, although I am not sure why. Any ideas?
(defun factor-primes (n)
(labels
((factor-primes-2 (n f)
(if (<= n 1)
nil
(if (zerop (mod n f))
(cons f (factor-primes-2 (/ n f) f))
took:
(factor-primes-2 n (1+ f))))))
(cons 1 (factor-primes-2 n 2))))
Regards
Gautham
In article
<····································@w24g2000prd.googlegroups.com>,
·············@gmail.com wrote:
> I am starting to learn Common Lisp with SLIME and "Practical Common
> Lisp" ...
>
> Now, I am trying to solve this question from http://projecteuler.net/.
>
> The prime factors of 13195 are 5, 7, 13 and 29.
> What is the largest prime factor of the number 600851475143 ?
>
> This is my answer.
>
> (defun find-largest-prime-factor
> (number)
> (do ((i 2 (1+
> i)))
> ((> i (/ number
> 2)))
> ;; if number is divisible by i
> (if ((lambda (x y) (if(zerop (rem x y))T)) number
> i)
> ;;Then try whether (number/i) is a prime and return
> if it is
> (if ((lambda
> (z)
> (loop for fac from 2 to (isqrt
> z)
> never (zerop (mod z fac)))) (/ number
> i))
> (return (/ number i))))))
>
> Then when I ran from SLIME ...
>
> CL-USER> (load "/media/Suboo/Programming/lisp/find-largest-prime-
> factor.cl")
> ; Loading #p"/media/Suboo/Programming/lisp/find-largest-prime-
> factor.cl".
> T
> CL-USER> (find-largest-prime-factor
> 13195)
> 29
> CL-USER> (find-largest-prime-factor
> 60085147514)
> 10976461
> CL-USER> (find-largest-prime-factor
> 600851475143)
> Here it hangs for a long time
>
> I waited around 5 minutes, still it doesn't print anything ..
> Why it is not working for the last one ?
> Is it because the number too large ?
> I am using SLIME with CMUCL ...
> Plz, help me ... I spend more than 2 hours to get that answer and now
> it is not working ;(
Right, get rid of the lambdas.
Also: if you type code to the CMUCL REPL it will
not be compiled to machine code.
Use (compile 'find-largest-prime-number) to compile the function.
--
http://lispm.dyndns.org/
t> Why it is not working for the last one ?
t> Is it because the number too large ?
yep, why not? why do you expect it to be fast?
actually algorithms are not supposed to be equally
fast -- some will run in a fraction of second, other will
require time larger than the time of existence of universe,
even on fastest computer possible.
you should at least roughly estimate pace at which
it is going -- that is, how many numbers per second
does it check -- and from this estimate how much
you have to wait. if it is too much, you might need
to find a better algorithm. Project Euler's tasks are
usually not some boring stuff that you can do with
two loops, but they require some non-trivial
approach.
e.g. if you check one million numbers per second,
to check 300000000000 of them you need about 3.5 days.
oops..
t> Plz, help me ... I spend more than 2 hours to get that answer and now
t> it is not working ;(
for some algorithms 2 billions years won't be enough..
it is pretty easy to monitor progress. first, you can
try to break into a program (Ctrl-C Ctrl-C), then if you're
lucky it jumps into a debugger, then you can inspect variable
i in function's stack to see how much progress did it make so
far.
another approach is to print current iteration while it goes,
i.e. insert (print i) after "do". if that is too much information,
you can print once in 1000 iterations or so, e.g.:
(when (zerop (mod i 1000)) (print i))
As you all pointed out, i think first I should shorten my function ...
So I wrote a function find factors ..
(defun find-factors (number)
(do ((i 2 (1+
i)))
((>= i (/ number
i)))
(if(zerop (rem number
i))
(format t "~a " i))))
* (find-factors 13195)
5 7 13 29 35 65 91
NIL
* (find-factors 600851475143)
71 839 1471 6857 59569 104441 486847
Then it works ! I just need to wait around 2 secs !
So, I was happy and saved the function to a file ...
And added functions prime and find-prime-factors ...
(defun find-factors (number)
(do ((i 2 (1+
i)))
((>= i (/ number
i)))
(if(zerop (rem number
i))
(format t "~a " i))))
(defun primep (number)
(loop for fac from 2 to (isqrt number)
never (zerop (mod number fac))))
(defun find-prime-factors (number)
(do ((i 2 (1+
i)))
((>= i (/ number
i)))
(if(zerop (rem number i))
(if(primep i)
(format t "~a " i)))))
Then I load the file from slime
CL-USER> (load (compile-file "/media/Suboo/Programming/lisp/find-
largest-prime-\
factor.cl"))
; Python version 1.1, VM version Intel x86 on 05 DEC 08 02:49:17
pm.
; Compiling: /media/Suboo/Programming/lisp/find-largest-prime-
factor.cl 05 DEC \
08 02:44:39
pm
; Converted FIND-
FACTORS.
; Compiling DEFUN FIND-
FACTORS:
; Converted
PRIMEP.
; Compiling DEFUN
PRIMEP:
; Converted FIND-PRIME-
FACTORS.
; Compiling DEFUN FIND-PRIME-
FACTORS:
; Byte Compiling Top-Level
Form:
; /media/Suboo/Programming/lisp/find-largest-prime-factor.x86f
written.
; Compilation finished in
0:00:00.
;
T
CL-USER> (find-factors
13195)
5 7 13 29 35 65 91
NIL
CL-USER> (primep
13)
T
CL-USER> (find-prime-factors
13195)
5 7 13 29
NIL
CL-USER> (find-factors
600851475143)
-uuu:**-F1 *slime-repl cmucl* Bot (26,0)
(REPL)--------------------------
[Commencing GC with 13.8 MB in use.]
Then when I tested with that 600851475143 it hangs as usual
What I cannot understand is when I first try, it works and when I try
again with the same function which is even compiled ... ....
So, i think it is not because of the algorithm ...
Ok, well for now .. I think i should better move on the another
lesson
as I cannot spend 2 billions years for this algorithm ;P
I already got the answer for the question ...
I just takes the factors, 71 839 1471 6857 59569 104441 486847, from
the first time when it works and tested whether they are primes or
not ...
Thank you all for your help !!!
In article
<····································@k36g2000pri.googlegroups.com>,
·············@gmail.com wrote:
A message from management: if you want to post longer amounts of lisp code,
do ***not*** use google groups. it inserts linebreaks, which makes
code hard to read. thank you, for your attention. ;-)
Either use a 'real' Usenet provider or use http://paste.lisp.org
and post the link here.
> As you all pointed out, i think first I should shorten my function ...
> So I wrote a function find factors ..
>
> (defun find-factors (number)
> (do ((i 2 (1+
> i)))
> ((>= i (/ number
> i)))
> (if(zerop (rem number
> i))
> (format t "~a " i))))
(defun find-factors (number)
(do ((i 2 (1+ i)))
((>= I (/ number i)))
(if (zerop (rem number i))
(format t "~a " i))))
(defun find-prime-factors (number)
(do ((i 2 (1+ i)))
((>= i (/ number i)))
(if (and (zerop (rem number i)) (primep i))
(format t "~a " i))))
(defun primep (number)
(loop for fac from 2 to (isqrt number)
never (zerop (mod number fac))))
Let's try it:
LispWorks
CL-USER 10 > (time (find-factors 600851475143))
Timing the evaluation of (FIND-FACTORS 600851475143)
71 839 1471 6857 59569 104441 486847
User time = 0.415
System time = 0.004
Elapsed time = 0.405
Allocation = 18723272 bytes
19 Page faults
NIL
SBCL
* (time (find-factors 600851475143))
71 839 1471 6857 59569 104441 486847
Evaluation took:
0.462 seconds of real time
0.458043 seconds of total run time (0.443513 user, 0.014530 system)
[ Run times consist of 0.003 seconds GC time, and 0.456 seconds non-GC time. ]
99.13% CPU
1,074,116,008 processor cycles
24,816,432 bytes consed
CLISP
[4]> (mapcar 'compile '(FIND-FACTORS FIND-PRIME-FACTORS PRIMEP))
(FIND-FACTORS FIND-PRIME-FACTORS PRIMEP)
[5]> (time (find-factors 600851475143))
71 839 1471 6857 59569 104441 486847
Real time: 1.284788 sec.
Run time: 1.274054 sec.
Space: 25161968 Bytes
GC: 27, GC time: 0.279237 sec.
NIL
@William James: show us the Ruby version!
>
>
> * (find-factors 13195)
> 5 7 13 29 35 65 91
> NIL
> * (find-factors 600851475143)
> 71 839 1471 6857 59569 104441 486847
>
> Then it works ! I just need to wait around 2 secs !
>
> So, I was happy and saved the function to a file ...
> And added functions prime and find-prime-factors ...
>
>
> (defun find-factors (number)
> (do ((i 2 (1+
> i)))
> ((>= i (/ number
> i)))
> (if(zerop (rem number
> i))
> (format t "~a " i))))
>
> (defun primep (number)
> (loop for fac from 2 to (isqrt number)
> never (zerop (mod number fac))))
>
>
> (defun find-prime-factors (number)
> (do ((i 2 (1+
> i)))
> ((>= i (/ number
> i)))
> (if(zerop (rem number i))
> (if(primep i)
> (format t "~a " i)))))
>
> Then I load the file from slime
>
> CL-USER> (load (compile-file "/media/Suboo/Programming/lisp/find-
> largest-prime-\
> factor.cl"))
>
> ; Python version 1.1, VM version Intel x86 on 05 DEC 08 02:49:17
> pm.
> ; Compiling: /media/Suboo/Programming/lisp/find-largest-prime-
> factor.cl 05 DEC \
> 08 02:44:39
> pm
>
> ; Converted FIND-
> FACTORS.
> ; Compiling DEFUN FIND-
> FACTORS:
> ; Converted
> PRIMEP.
> ; Compiling DEFUN
> PRIMEP:
> ; Converted FIND-PRIME-
> FACTORS.
> ; Compiling DEFUN FIND-PRIME-
> FACTORS:
> ; Byte Compiling Top-Level
> Form:
>
> ; /media/Suboo/Programming/lisp/find-largest-prime-factor.x86f
> written.
> ; Compilation finished in
> 0:00:00.
> ;
> T
>
> CL-USER> (find-factors
> 13195)
> 5 7 13 29 35 65 91
> NIL
> CL-USER> (primep
> 13)
> T
> CL-USER> (find-prime-factors
> 13195)
> 5 7 13 29
> NIL
> CL-USER> (find-factors
> 600851475143)
>
> -uuu:**-F1 *slime-repl cmucl* Bot (26,0)
> (REPL)--------------------------
> [Commencing GC with 13.8 MB in use.]
>
> Then when I tested with that 600851475143 it hangs as usual
> What I cannot understand is when I first try, it works and when I try
> again with the same function which is even compiled ... ....
> So, i think it is not because of the algorithm ...
> Ok, well for now .. I think i should better move on the another
> lesson
> as I cannot spend 2 billions years for this algorithm ;P
>
> I already got the answer for the question ...
> I just takes the factors, 71 839 1471 6857 59569 104441 486847, from
> the first time when it works and tested whether they are primes or
> not ...
>
> Thank you all for your help !!!
--
http://lispm.dyndns.org/
* ·············@gmail.com
Wrote on Fri, 5 Dec 2008 07:56:36 -0800 (PST):
| Now, I found out what is wrong !!!
| I switch to sbcl + SLIME from cmucl ...
| All of the functions above are working fine now ....
The problem probably wasnt in CMUCL because your functions ran fine in
my CMUCL.
--
Madhu
>
> (defun find-factors (number)
> (do ((i 2 (1+ i)))
> ((>= I (/ number i)))
> (if (zerop (rem number i))
> (format t "~a " i))))
Change find-factors to
(defun find-factors (number)
(do ((i 2 (1+ i)))
((< number (* i i)))
(if (zerop (rem number i))
(format t "~a " i))))
Runs about 10x faster.
SBCL
* (defun find-factors (number)
(do ((i 2 (1+ i)))
((< number (* i i)))
(if (zerop (rem number i))
(format t "~a " i))))
STYLE-WARNING: redefining FIND-FACTORS in DEFUN
FIND-FACTORS
* (time (find-factors 600851475143))
71 839 1471 6857 59569 104441 486847
Evaluation took:
0.072 seconds of real time
0.060004 seconds of user run time
0.0 seconds of system run time
0 calls to %EVAL
0 page faults and
16,384 bytes consed.
NIL
*
Wade <·············@gmail.com> writes:
> FIND-FACTORS
> * (time (find-factors 600851475143))
> 71 839 1471 6857 59569 104441 486847
> Evaluation took:c
> 0.072 seconds of real time
> 0.060004 seconds of user run time
BTW, is this one allowed?
(defun find-factors (number)
(loop with root = (isqrt number)
for i from 2 while (<= i root)
when (zerop (rem number i))
do (return-from find-factors
(cons i (find-factors (/ number i)))))
(list number))
(time (find-factors 600851475143)) ; SBCL
Evaluation took:
0.000 seconds of real time
0.000000 seconds of total run time (0.000000 user, 0.000000 system)
100.00% CPU
763,518 processor cycles
32,752 bytes consed
(71 839 1471 6857)
Nicolas
From: William James
Subject: Re: Another Newbie Question !!!
Date:
Message-ID: <ghelvc$mrr$1@aioe.org>
Nicolas Neuss wrote:
> Wade <·············@gmail.com> writes:
>
> > FIND-FACTORS
> > * (time (find-factors 600851475143))
> > 71 839 1471 6857 59569 104441 486847
> > Evaluation took:c
> > 0.072 seconds of real time
> > 0.060004 seconds of user run time
>
> BTW, is this one allowed?
>
> (defun find-factors (number)
> (loop with root = (isqrt number)
> for i from 2 while (<= i root)
> when (zerop (rem number i))
> do (return-from find-factors
> (cons i (find-factors (/ number i)))))
> (list number))
>
> (time (find-factors 600851475143)) ; SBCL
> Evaluation took:
> 0.000 seconds of real time
> 0.000000 seconds of total run time (0.000000 user, 0.000000 system)
> 100.00% CPU
> 763,518 processor cycles
> 32,752 bytes consed
> (71 839 1471 6857)
Correct results:
71 839 1471 6857 59569 104441 486847
William James <·········@yahoo.com> wrote:
+---------------
| Nicolas Neuss wrote:
| > BTW, is this one allowed?
| > (defun find-factors (number)
| > (loop with root = (isqrt number)
| > for i from 2 while (<= i root)
| > when (zerop (rem number i))
| > do (return-from find-factors
| > (cons i (find-factors (/ number i)))))
| > (list number))
| >
| > (time (find-factors 600851475143)) ; SBCL
...
| > (71 839 1471 6857)
|
| Correct results:
|
| 71 839 1471 6857 59569 104441 486847
+---------------
Depends on what you mean by "correct". Nicolas's answer is
correct inasmuch as (* 71 839 1471 6857) ==> 600851475143.
Your answer repeats factors that have already been accounted
for earlier:
59569 = (* 71 839)
104441 = (* 71 1471)
486847 = (* 71 6857)
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
····@rpw3.org (Rob Warnock) writes:
> William James <·········@yahoo.com> wrote:
> | ...
> | Correct results:
> |
> | 71 839 1471 6857 59569 104441 486847
> +---------------
>
> Depends on what you mean by "correct". Nicolas's answer is
> correct inasmuch as (* 71 839 1471 6857) ==> 600851475143.
>
> Your answer repeats factors that have already been accounted
> for earlier:
>
> 59569 = (* 71 839)
> 104441 = (* 71 1471)
> 486847 = (* 71 6857)
And if one should really want ALL factors, one can get them from the prime
factors as follows:
(mapcar (lambda (list) (apply #'* list))
(nonempty-subsets (find-factors 600851475143)))
where NONEMPTY-SUBSETS is from your favorite toolbox. This yields
(71 839 1471 6857 59569 104441 486847 1234169 5753023 10086647 87625999
408464633 716151937 8462696833 600851475143)
Nicolas
P.S.: Here is code for NONEMPTY-SUBSETS from my utilities (in my PDE solver
Femlisp). Similar routines are probably also in Alexandria.
(defun k-subsets (set k)
"Returns all subsets of @arg{set} with length @arg{k}. Example:
@lisp
(k-subsets '(1 2 3) 2)
@result{} ((1 2) (1 3) (2 3))
@end lisp"
(cond ((minusp k) '())
((zerop k) (list '()))
((= k 1) (mapcar #'list set))
(t (loop for elems on set
nconc (mapcar #'(lambda (set) (cons (car elems) set))
(k-subsets (cdr elems) (- k 1)))))))
(defun k->l-subsets (set k l)
"Returns all subsets of @arg{set} with length between @arg{k} and
@arg{l}. Example:
@lisp
(k->l-subsets '(1 2 3) 1 2) @result{}
((1) (2) (3) (1 2) (1 3) (2 3))
@end lisp"
(loop for i from k to l
nconc (k-subsets set i)))
(defun subsets (set)
"Returns a list of all subsets of @arg{set}."
(k->l-subsets set 0 (length set)))
(defun nonempty-subsets (set)
"Returns a list of all nonempty subsets of @arg{set}."
(k->l-subsets set 1 (length set)))
From: Albert Krewinkel
Subject: Docstrings, was: Another Newbie Question !!!
Date:
Message-ID: <m27i6b92dq.fsf_-_@gmx.net>
Nicolas Neuss <········@math.uni-karlsruhe.de> writes:
> P.S.: Here is code for NONEMPTY-SUBSETS from my utilities (in my PDE solver
> Femlisp). Similar routines are probably also in Alexandria.
>
> (defun k-subsets (set k)
> "Returns all subsets of @arg{set} with length @arg{k}. Example:
> @lisp
> (k-subsets '(1 2 3) 2)
> @result{} ((1 2) (1 3) (2 3))
> @end lisp"
> (cond ((minusp k) '())
> ((zerop k) (list '()))
> ((= k 1) (mapcar #'list set))
> (t (loop for elems on set
> nconc (mapcar #'(lambda (set) (cons (car elems) set))
> (k-subsets (cdr elems) (- k 1)))))))
>
> (defun k->l-subsets (set k l)
> "Returns all subsets of @arg{set} with length between @arg{k} and
> @arg{l}. Example:
> @lisp
> (k->l-subsets '(1 2 3) 1 2) @result{}
> ((1) (2) (3) (1 2) (1 3) (2 3))
> @end lisp"
> (loop for i from k to l
> nconc (k-subsets set i)))
>
> (defun subsets (set)
> "Returns a list of all subsets of @arg{set}."
> (k->l-subsets set 0 (length set)))
>
> (defun nonempty-subsets (set)
> "Returns a list of all nonempty subsets of @arg{set}."
> (k->l-subsets set 1 (length set)))
I notice that you use a special notation to mark arguments and code
examples in your docstrings. Are you using those to generate some kind
of markup documentation? I feel that this is something seriously
missing from my toolbox, so I'd be glad to learn about every tool which
might resolve this shortcomming.
Thanks,
Albert
Albert Krewinkel <·········@gmx.net> writes:
> I notice that you use a special notation to mark arguments and code
> examples in your docstrings. Are you using those to generate some kind
> of markup documentation? I feel that this is something seriously missing
> from my toolbox, so I'd be glad to learn about every tool which might
> resolve this shortcomming.
@command{...} is Texinfo syntax. For automatic generation of the Femlisp
manual, I use an docstring extractor which is derived from
"docstrings.lisp" in SBCL (this file has also changed in the meantime). Up
to now, I have not yet included this in the Femlisp distribution, mainly
because the process still requires some handwork.
Yours, Nicolas
On 2008-12-09, Nicolas Neuss <········@math.uni-karlsruhe.de> wrote:
> Albert Krewinkel <·········@gmx.net> writes:
>
>> I notice that you use a special notation to mark arguments and code
>> examples in your docstrings. Are you using those to generate some kind
>> of markup documentation? I feel that this is something seriously missing
>> from my toolbox, so I'd be glad to learn about every tool which might
>> resolve this shortcomming.
These days, my impression is that we don't have too few documentation
tools, but almost "too many".
"Too many" in the sense that there's a tool for every itch a developer
wanted to scratch regarding documentation for Lisp (which is great!
documentation is good), but they are all incompatible.
For example, there's the SBCL code Nicolas already mentioned. It parses
docstrings in SBCL's syntax and generates texinfo.
Then there's my solution called atdoc[2], which parses a special "atdoc
syntax" and generates HTML.
(See also the often copied documentation-template, the much maligned
tinaa, clixdoc, Michael Weber's ideas for reverse texinfo->docstring
reversions, etc)
While there will always be many different approaches to documentation
generation, wouldn't it be much better if you could at least combine all
the different projects? For example, someone who isn't a fan of atdoc's
syntax (which is vaguely inspired by javadoc and texinfo) might want to
parse SBCL-style strings, but also use atdoc to generate HTML from that.
That's why I'm currently trying to come up with a concept for a more
modular approach.
> @command{...} is Texinfo syntax. For automatic generation of the Femlisp
> manual, I use an docstring extractor which is derived from
> "docstrings.lisp" in SBCL (this file has also changed in the meantime). Up
> to now, I have not yet included this in the Femlisp distribution, mainly
> because the process still requires some handwork.
Luis Oliveira is working on a conversion of docstrings.lisp as a
stand-alone project called texinfo-docstrings[1].
Since then, Nikodemus Siivola has refactored docstrings.lisp to parse
documentation into a CLOS representation, which would be independent of
the input syntax and output format.
My plan is to forward-port those changes to texinfo-docstrings, and
modularize it further, turning the docstring parser into a reusable
library that parses strings into that CLOS representation.
My hope is that a documented CLOSy docstring API would help reduce code
duplication. I'm certain most Lispers will still hack their own
documentation solutions, but at least they could re-use existing
libraries for parts of that work.
d.
[1] http://repo.or.cz/w/texinfo-docstrings.git
[2] http://www.lichteblau.com/atdoc/doc/
Example: http://common-lisp.net/project/plexippus-xpath/atdoc/index.html
From: William James
Subject: Re: Another Newbie Question !!!
Date:
Message-ID: <ghcrgb$pl7$1@aioe.org>
Rainer Joswig wrote:
> (defun find-factors (number)
> (do ((i 2 (1+ i)))
> ((>= I (/ number i)))
> (if (zerop (rem number i))
> (format t "~a " i))))
>
> Let's try it:
>
> LispWorks
>
> CL-USER 10 > (time (find-factors 600851475143))
> Timing the evaluation of (FIND-FACTORS 600851475143)
> 71 839 1471 6857 59569 104441 486847
> User time = 0.415
> System time = 0.004
> Elapsed time = 0.405
> Allocation = 18723272 bytes
> 19 Page faults
> NIL
>
> @William James: show us the Ruby version!
You win.
As you surmised, Ruby is a slow nag when it comes to looping.
So let's use Tilton's favorite new Language, JavaScript!
SpiderMonkey and jslibs:
LoadModule('jsstd') // Gives us Print().
function find_factors( number )
{ var i = 2
do if ( 0 == number % i ) Print(i, " ")
while( ++i <= number / i )
}
find_factors( 600851475143 )
--- 2.8 GHz machine ---
--- timed with Ultra Precision Command Timer 1.6 ---
71 839 1471 6857 59569 104441 486847
Command executed:
C:\WINDOWS\SYSTEM32\COMMAND.COM /C js factors.js
Parameters: factors.js
Raw total count: 321806 cycles on the 8253/4 programmable
interval timer.
Elapsed time: 269704.1 microseconds = 0.2697 seconds.
JavaScript wins! And TraceMonkey will be even faster!
Rejoice, repent, and be pasteurized!
······@corporate-world.lisp.de schrieb:
> (defun find-factors (number)
> (loop with i = 2
> when (zerop (rem number i)) do (format t "~a " i)
> while (<= (incf i) (truncate number i))))
>
> CL-USER 48 > (time (find-factors 600851475143))
> Timing the evaluation of (FIND-FACTORS 600851475143)
> 71 839 1471 6857 59569 104441 486847
> User time = 0.076
> System time = 0.001
> Elapsed time = 0.063
> Allocation = 112888 bytes
> 20 Page faults
> NIL
Hallo Rainer.
I copy&pasted your code into Lispwork Professional 5.1 and got very
different results. My timing gave me about 400 msecs.
Did you set some optimization settings somewhere else? Or do you have
access to one of the fastest CPUs in the world? ;-)
I used a pretty nice machine and Lispworks, like you, so I am surprised
that the results are that different.
I tried it then on sbcl under Linux on the same machine, but inside a
VM (costs maybe 10% efficiency) and got a timing of about 200 msecs.
I was curious to see how fast it would run in Clojure on that box
and got a slow runtime without giving type hints.
Probably somewhere near Ruby performance I guess.
Rich Hickey was so kind to give direct access to Javas modulo operator,
which I then used, along with direct access to division and with two
type hints:
(defn find-factors [#^Long n]
(loop [#^Long i 2, result []]
(if (> i (unchecked-divide n i)) result
(recur (inc i) (if (zero? (unchecked-remainder n i)) (conj
result i) result)))))
user> (time (find-factors 600851475143))
"Elapsed time: 105.362271 msecs"
[71 839 1471 6857 59569 104441 486847]
I made a Java version and let it run inside a server jvm. This did its
work within 16 msecs.
With some type declarations one could do this in Lisp maybe as well.
Anyway, I used a new Intel Core2 Duo E7300 @ 2,66 GHz, 2GB Ram
under XP with Servicepack 3. That gave me the results I posted above.
Andr�
--
On 11 Dez., 09:20, André Thieme <address.good.until.
···········@justmail.de> wrote:
> ······@corporate-world.lisp.de schrieb:
>
> > (defun find-factors (number)
> > (loop with i = 2
> > when (zerop (rem number i)) do (format t "~a " i)
> > while (<= (incf i) (truncate number i))))
>
> > CL-USER 48 > (time (find-factors 600851475143))
> > Timing the evaluation of (FIND-FACTORS 600851475143)
> > 71 839 1471 6857 59569 104441 486847
> > User time = 0.076
> > System time = 0.001
> > Elapsed time = 0.063
> > Allocation = 112888 bytes
> > 20 Page faults
> > NIL
>
> Hallo Rainer.
> I copy&pasted your code into Lispwork Professional 5.1 and got very
> different results. My timing gave me about 400 msecs.
> Did you set some optimization settings somewhere else? Or do you have
> access to one of the fastest CPUs in the world? ;-)
> I used a pretty nice machine and Lispworks, like you, so I am surprised
> that the results are that different.
Did you try the 64bit version of LispWorks? It is much faster than the
32bit version.
>
> I tried it then on sbcl under Linux on the same machine, but inside a
> VM (costs maybe 10% efficiency) and got a timing of about 200 msecs.
>
> I was curious to see how fast it would run in Clojure on that box
> and got a slow runtime without giving type hints.
> Probably somewhere near Ruby performance I guess.
> Rich Hickey was so kind to give direct access to Javas modulo operator,
> which I then used, along with direct access to division and with two
> type hints:
>
> (defn find-factors [#^Long n]
> (loop [#^Long i 2, result []]
> (if (> i (unchecked-divide n i)) result
> (recur (inc i) (if (zero? (unchecked-remainder n i)) (conj
> result i) result)))))
>
> user> (time (find-factors 600851475143))
> "Elapsed time: 105.362271 msecs"
> [71 839 1471 6857 59569 104441 486847]
It doesn't print like my code above, AFAICS.
>
> I made a Java version and let it run inside a server jvm. This did its
> work within 16 msecs.
> With some type declarations one could do this in Lisp maybe as well.
>
> Anyway, I used a new Intel Core2 Duo E7300 @ 2,66 GHz, 2GB Ram
> under XP with Servicepack 3. That gave me the results I posted above.
>
> André
> --
······@corporate-world.lisp.de schrieb:
> On 11 Dez., 09:20, Andr� Thieme <address.good.until.
> ···········@justmail.de> wrote:
>> ······@corporate-world.lisp.de schrieb:
>>
>>> (defun find-factors (number)
>>> (loop with i = 2
>>> when (zerop (rem number i)) do (format t "~a " i)
>>> while (<= (incf i) (truncate number i))))
>>> CL-USER 48 > (time (find-factors 600851475143))
>>> Timing the evaluation of (FIND-FACTORS 600851475143)
>>> 71 839 1471 6857 59569 104441 486847
>>> User time = 0.076
>>> System time = 0.001
>>> Elapsed time = 0.063
>>> Allocation = 112888 bytes
>>> 20 Page faults
>>> NIL
>> Hallo Rainer.
>> I copy&pasted your code into Lispwork Professional 5.1 and got very
>> different results. My timing gave me about 400 msecs.
>> Did you set some optimization settings somewhere else? Or do you have
>> access to one of the fastest CPUs in the world? ;-)
>> I used a pretty nice machine and Lispworks, like you, so I am surprised
>> that the results are that different.
>
> Did you try the 64bit version of LispWorks? It is much faster than the
> 32bit version.
Okay, I understand. This means that these big numbers were of type fixnum
for your Lisp and it was able to do calculations in the cpu registers.
The Java version did that more or less too, with its 64 bit �long�.
Although this still was an emulation on my 32 bit machine.
So on a 64 bit Windows Lispworks would have performed much better and
Java (and Clojure) a little bit.
>> (defn find-factors [#^Long n]
>> (loop [#^Long i 2, result []]
>> (if (> i (unchecked-divide n i)) result
>> (recur (inc i) (if (zero? (unchecked-remainder n i)) (conj
>> result i) result)))))
>>
>> user> (time (find-factors 600851475143))
>> "Elapsed time: 105.362271 msecs"
>> [71 839 1471 6857 59569 104441 486847]
>
> It doesn't print like my code above, AFAICS.
Right, this just returns a vector with the results.
Although I just let it print the intermediate results for each insertion
into the result vector and it did not really change the timing.
It varies between 103 and 110 msecs, with and without.
Andr�
--
On 11 Dez., 22:53, André Thieme <address.good.until.
···········@justmail.de> wrote:
> ······@corporate-world.lisp.de schrieb:
>
>
>
> > On 11 Dez., 09:20, André Thieme <address.good.until.
> > ···········@justmail.de> wrote:
> >> ······@corporate-world.lisp.de schrieb:
>
> >>> (defun find-factors (number)
> >>> (loop with i = 2
> >>> when (zerop (rem number i)) do (format t "~a " i)
> >>> while (<= (incf i) (truncate number i))))
> >>> CL-USER 48 > (time (find-factors 600851475143))
> >>> Timing the evaluation of (FIND-FACTORS 600851475143)
> >>> 71 839 1471 6857 59569 104441 486847
> >>> User time = 0.076
> >>> System time = 0.001
> >>> Elapsed time = 0.063
> >>> Allocation = 112888 bytes
> >>> 20 Page faults
> >>> NIL
> >> Hallo Rainer.
> >> I copy&pasted your code into Lispwork Professional 5.1 and got very
> >> different results. My timing gave me about 400 msecs.
> >> Did you set some optimization settings somewhere else? Or do you have
> >> access to one of the fastest CPUs in the world? ;-)
> >> I used a pretty nice machine and Lispworks, like you, so I am surprised
> >> that the results are that different.
>
> > Did you try the 64bit version of LispWorks? It is much faster than the
> > 32bit version.
>
> Okay, I understand. This means that these big numbers were of type fixnum
> for your Lisp and it was able to do calculations in the cpu registers.
> The Java version did that more or less too, with its 64 bit “long”.
> Although this still was an emulation on my 32 bit machine.
> So on a 64 bit Windows Lispworks would have performed much better and
> Java (and Clojure) a little bit.
The good thing under Mac OS X is that both versions (32bit and 64bit)
of LispWorks are running on a 64bit Intel CPU. Even the development
environment
now works in both versions. Drawback: the 64bit version is only
available
as expensive Enterprise Edition (and does not include the 32bit
version).
The speed up can be also felt when using the IDE. It is much snappier.
Generally I would say that on my Mac the 64bit version is about twice
as fast over a whole bunch of benchmarks. Once one has used the 64bit
LispWorks version it is hard to go back to the 32bit version. The
Cocoa-based IDE combined with a 64bit LispWorks is my current favorite
Lisp IDE.
End of marketing message. ;-)
>
> >> (defn find-factors [#^Long n]
> >> (loop [#^Long i 2, result []]
> >> (if (> i (unchecked-divide n i)) result
> >> (recur (inc i) (if (zero? (unchecked-remainder n i)) (conj
> >> result i) result)))))
>
> >> user> (time (find-factors 600851475143))
> >> "Elapsed time: 105.362271 msecs"
> >> [71 839 1471 6857 59569 104441 486847]
>
> > It doesn't print like my code above, AFAICS.
>
> Right, this just returns a vector with the results.
> Although I just let it print the intermediate results for each insertion
> into the result vector and it did not really change the timing.
> It varies between 103 and 110 msecs, with and without.
>
> André
> --
=?windows-1252?Q?Andr=E9_Thieme?= <······························@justmail.de> writes:
> ······@corporate-world.lisp.de schrieb:
> > (defun find-factors (number)
> > (loop with i = 2
> > when (zerop (rem number i)) do (format t "~a " i)
> > while (<= (incf i) (truncate number i))))
> > CL-USER 48 > (time (find-factors 600851475143))
> > Timing the evaluation of (FIND-FACTORS 600851475143)
> > 71 839 1471 6857 59569 104441 486847
> > User time = 0.076
> > System time = 0.001
> > Elapsed time = 0.063
> > Allocation = 112888 bytes
> > 20 Page faults
> > NIL
>
> Hallo Rainer.
> I copy&pasted your code into Lispwork Professional 5.1 and got very
> different results. My timing gave me about 400 msecs.
> Did you set some optimization settings somewhere else? Or do you have
> access to one of the fastest CPUs in the world? ;-)
> I used a pretty nice machine and Lispworks, like you, so I am surprised
> that the results are that different.
Well, to really get reliable timings you need to insert
(compile 'find-factors)
into your script between the DEFUN and the TIME steps. Some lisps will
automatically compile functions (IIRC CMUCL, SBCL and CCL do this) while
others will use a separate (and slower) interpreter (LispWorks, ACL).
So make sure you are really timing a compiled function if you want the
numbers to actually mean anything.
--
Thomas A. Russ, USC/Information Sciences Institute
Thomas A. Russ <···@sevak.isi.edu> wrote:
+---------------
| Well, to really get reliable timings you need to insert
| (COMPILE 'FIND-FACTORS) into your script between the DEFUN
| and the TIME steps. Some lisps will automatically compile
| functions (IIRC CMUCL, SBCL and CCL do this) while others
| will use a separate (and slower) interpreter (LispWorks, ACL).
+---------------
While that is true for SBCL, CMUCL still retains its interpreter,
which is used by default unless functions are explicitly compiled.
What sometimes confuses people is the fact that CMUCL automatically
"converts" or "minimally compiles" (CLHS 3.2.2.2) functions the
first time they are called[1], and that this "conversion" includes
macro expansion, so that if a macro is redefined even interpreted
functions [if they've already been "converted"] have to be redefined
in order to pick up the new macro definition. So to this extent (only)
CMUCL's REPL behaves as if everything typed to the REPL is "compiled".
But in actual fact, even such "converted" functions still remain
truly interpreted unless/until explicitly compiled:
cmu> (defmacro my-quote (form)
(format *debug-io* "MY-QUOTE expanded to: ~s~%" form)
form)
MY-QUOTE
cmu> (defun foo (x)
(+ x (my-quote 52)))
FOO
cmu> #'foo
#<Interpreted Function FOO {489BE389}>
cmu> (foo 5) ; First usage, function gets "converted".
MY-QUOTE expanded to: 52
57
cmu> (foo 10) ; Notice that MY-QUOTE is *not* expanded again.
62
cmu> #'foo ; Yet FOO is still an interpreted function
#<Interpreted Function FOO {489D02E1}>
cmu>
Macros do get expanded one more time when a function is truly compiled:
cmu> (compile 'foo)
MY-QUOTE expanded to: 52
; Compiling LAMBDA (X):
; Compiling Top-Level Form:
FOO
NIL
NIL
cmu> #'foo ; Now a compiled function.
#<Function FOO {489EC781}>
cmu> (foo 17) ; No further expansion.
69
cmu>
-Rob
[1] This noticeably helps the performance of "scripts" containing many
functions of which only a few are called during any given execution.
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
thus spoke William James <·········@yahoo.com>:
>> @William James: show us the Ruby version!
> You win.
> As you surmised, Ruby is a slow nag when it comes to looping.
Arithmetic operations. Having to do dynamic method dispatch upon every
addition or division is the prime factor here.
--
The great peril of our existence lies in the fact that our diet consists
entirely of souls. -- Inuit saying
On 2008-12-05, Rainer Joswig <······@lisp.de> wrote:
> In article
><····································@k36g2000pri.googlegroups.com>,
> ·············@gmail.com wrote:
>
>
> A message from management: if you want to post longer amounts of lisp code,
> do ***not*** use google groups. it inserts linebreaks, which makes
> code hard to read. thank you, for your attention. ;-)
>
> Either use a 'real' Usenet provider or use http://paste.lisp.org
> and post the link here.
>
>> As you all pointed out, i think first I should shorten my function ...
>> So I wrote a function find factors ..
>>
>> (defun find-factors (number)
>> (do ((i 2 (1+
>> i)))
>> ((>= i (/ number
>> i)))
>> (if(zerop (rem number
>> i))
>> (format t "~a " i))))
>
> (defun find-factors (number)
> (do ((i 2 (1+ i)))
> ((>= I (/ number i)))
> (if (zerop (rem number i))
> (format t "~a " i))))
If called for 6, this finds only 2, but not 3.
Should be called FIND-FACTORS-SMALLER-THAN-SQRT. :)
If you use TRUNCATE instead of /, you get the approximate quotient and
remainder simultaneously, which you can take advantage of:
(defun find-factors-2 (number)
(do ((i 2)
(rem 0)
(quot number) out)
((> i quot) out)
(multiple-value-setq (quot rem) (truncate number i))
(when (zerop rem)
(push i out))
(incf i)))
Can you benchmark that? Also a version of your function with simply
/ replaced with TRUNCATE.
> LispWorks
>
> CL-USER 10 > (time (find-factors 600851475143))
> Timing the evaluation of (FIND-FACTORS 600851475143)
> 71 839 1471 6857 59569 104441 486847
> User time = 0.415
> System time = 0.004
> Elapsed time = 0.405
> Allocation = 18723272 bytes
> 19 Page faults
> NIL
CLISP:
This is on:
$ cat /proc/cpuinfo
processor : 0
vendor_id : AuthenticAMD
cpu family : 15
model : 33
model name : Dual Core AMD Opteron(tm) Processor 270
stepping : 2
cpu MHz : 2004.727
;; original
(time (find-factors 600851475143))
Real time: 1.097392 sec.
Run time: 1.096068 sec.
Space: 25499288 Bytes
GC: 49, GC time: 0.136009 sec.
(486847 104441 59569 6857 1471 839 71)
;; original with / replaced by TRUNCATE:
(time (find-factors 600851475143))
Real time: 0.40264 sec.
Run time: 0.400025 sec.
Space: 1146040 Bytes
GC: 2, GC time: 0.008 sec.
(486847 104441 59569 6857 1471 839 71)
;; mine
(time (find-factors-2 600851475143))
Real time: 0.298737 sec.
Run time: 0.296018 sec.
Space: 573048 Bytes
GC: 1, GC time: 0.004001 sec.
(486847 104441 59569 6857 1471 839 71)
Native compiling doesn't help here much; bignum lib performance does.
On Dec 6, 12:17 pm, Kaz Kylheku <········@gmail.com> wrote:
> On 2008-12-05, Rainer Joswig <······@lisp.de> wrote:
>
>
>
> > In article
> ><····································@k36g2000pri.googlegroups.com>,
> > ·············@gmail.com wrote:
>
> > A message from management: if you want to post longer amounts of lisp code,
> > do ***not*** use google groups. it inserts linebreaks, which makes
> > code hard to read. thank you, for your attention. ;-)
>
> > Either use a 'real' Usenet provider or usehttp://paste.lisp.org
> > and post the link here.
>
> >> As you all pointed out, i think first I should shorten my function ...
> >> So I wrote a function find factors ..
>
> >> (defun find-factors (number)
> >> (do ((i 2 (1+
> >> i)))
> >> ((>= i (/ number
> >> i)))
> >> (if(zerop (rem number
> >> i))
> >> (format t "~a " i))))
>
> > (defun find-factors (number)
> > (do ((i 2 (1+ i)))
> > ((>= I (/ number i)))
> > (if (zerop (rem number i))
> > (format t "~a " i))))
>
> If called for 6, this finds only 2, but not 3.
>
> Should be called FIND-FACTORS-SMALLER-THAN-SQRT. :)
>
> If you use TRUNCATE instead of /, you get the approximate quotient and
> remainder simultaneously, which you can take advantage of:
>
> (defun find-factors-2 (number)
> (do ((i 2)
> (rem 0)
> (quot number) out)
> ((> i quot) out)
> (multiple-value-setq (quot rem) (truncate number i))
> (when (zerop rem)
> (push i out))
> (incf i)))
>
> Can you benchmark that? Also a version of your function with simply
> / replaced with TRUNCATE.
CL-USER 59 > (time (find-factors-2 600851475143))
Timing the evaluation of (FIND-FACTORS-2 600851475143)
User time = 0.045
System time = 0.000
Elapsed time = 0.034
Allocation = 108688 bytes
0 Page faults
(486847 104441 59569 6857 1471 839 71)
The other one with /
CL-USER 62 > (time (find-factors 600851475143))
Timing the evaluation of (FIND-FACTORS 600851475143)
71 839 1471 6857 59569 104441 486847
User time = 0.410
System time = 0.004
Elapsed time = 0.402
Allocation = 18727376 bytes
10 Page faults
NIL
Modellname: MacBook Pro 17"
Modell-Identifizierung: MacBookPro2,1
Prozessortyp: Intel Core 2 Duo
Prozessorgeschwindigkeit: 2.33 GHz
Anzahl der Prozessoren: 1
Gesamtzahl der Kerne: 2
L2-Cache: 4 MB
Speicher: 3 GB
Busgeschwindigkeit: 667 MHz
>
> > LispWorks
>
> > CL-USER 10 > (time (find-factors 600851475143))
> > Timing the evaluation of (FIND-FACTORS 600851475143)
> > 71 839 1471 6857 59569 104441 486847
> > User time = 0.415
> > System time = 0.004
> > Elapsed time = 0.405
> > Allocation = 18723272 bytes
> > 19 Page faults
> > NIL
>
> CLISP:
>
> This is on:
>
> $ cat /proc/cpuinfo
> processor : 0
> vendor_id : AuthenticAMD
> cpu family : 15
> model : 33
> model name : Dual Core AMD Opteron(tm) Processor 270
> stepping : 2
> cpu MHz : 2004.727
>
> ;; original
> (time (find-factors 600851475143))
> Real time: 1.097392 sec.
> Run time: 1.096068 sec.
> Space: 25499288 Bytes
> GC: 49, GC time: 0.136009 sec.
> (486847 104441 59569 6857 1471 839 71)
>
> ;; original with / replaced by TRUNCATE:
> (time (find-factors 600851475143))
> Real time: 0.40264 sec.
> Run time: 0.400025 sec.
> Space: 1146040 Bytes
> GC: 2, GC time: 0.008 sec.
> (486847 104441 59569 6857 1471 839 71)
>
> ;; mine
> (time (find-factors-2 600851475143))
> Real time: 0.298737 sec.
> Run time: 0.296018 sec.
> Space: 573048 Bytes
> GC: 1, GC time: 0.004001 sec.
> (486847 104441 59569 6857 1471 839 71)
>
> Native compiling doesn't help here much; bignum lib performance does.
·············@gmail.com writes:
> Then I load the file from slime
>
...
> NIL
> CL-USER> (find-factors
> 600851475143)
>
> -uuu:**-F1 *slime-repl cmucl* Bot (26,0)
> (REPL)--------------------------
> [Commencing GC with 13.8 MB in use.]
>
> Then when I tested with that 600851475143 it hangs as usual
> What I cannot understand is when I first try, it works and when I try
> again with the same function which is even compiled ... ....
Well, I would take a look at the buffer *inferior-lisp*, and see if
there is anything in the way of an error message there. That way you
can at least rule out an underlying problem with the lisp.
In fact, if you don't find a problem in that buffer, try invoking your
function directly in the *inferior-lisp* buffer itself.
Assuming that works, you will have isolated the problem to some sort of
Slime-CMUCL interaction problem.
--
Thomas A. Russ, USC/Information Sciences Institute
From: Robert Maas, http://tinyurl.com/uh3t
Subject: Re: Another Newbie Question !!!
Date:
Message-ID: <REM-2008dec08-001@Yahoo.Com>
> From: ·············@gmail.com
> ... http://projecteuler.net/ ...
I glanced at the first two pages there, a curious set of math puzzles.
The following problem is too easy:
<http://projecteuler.net/index.php?section=problems&id=79>
I solved it manually, simply by drawing a graph of the first
triple, then scanning down the list to find other triples that
could be easily fitted into the graph by extrapolating off either
end or interpolating in the middle. I ended up with a sequence of
eight digits with no repeats, and going back through the list of
triples, checking them *all*, I saw that indeed I had the solution
already. If I had known ahead of time that no digit was repeated,
then I wouldn't have needed triples at all, pairs would have been
enough to establish the unique total ordering consistent with all
ordered pairs.
A more interesting/difficult problem, which is actually what I
expected at the outset, and what my graph-extending algorithm was
designed to solve, is where the password has at least one digit
repeated in two non-adjacent locations, but the bank deliberately
arranges to always ask for three digits not containing both of the
repeats of that one digit, thus no triple shows the repeat
directly. Then only some of the triples containing that repeated
digit would be mutually consistent with each other as sub-strings
of a single non-repeat sequence, the rest of the triples containing
the repeated digit would be consistent with a different non-repeat
sequence (where the single repeat digit has simply moved from one
location to the other within the rest of the sequence), and all the
triples not containing that repeated digit are consistent with both
non-repeating sequences.