Hi Alex, Joh-Tob,
Thank you. With the Knuth reference the code makes a lot more sense!
I had implemented a more basic version.
For large ranges, the performance difference of the Alex's iterative
version that utilizes the sequence is much better! It is a very nice use of
circular lists.
: (bench (for X 3000000 (prime-factors X)))
16.547 sec
-> (2 2 2 2 2 2 3 5 5 5 5 5 5)
: (bench (for X 3000000 (primeFactorz X)))
24.632 sec
-> (5 5 5 5 5 5 3 2 2 2 2 2 2)
: (bench (prime-factors 100000000000))
0.000 sec
-> (2 2 2 2 2 2 2 2 2 2 2 5 5 5 5 5 5 5 5 5 5 5)
: (bench (primeFactorz 100000000000))
0.000 sec
-> (5 5 5 5 5 5 5 5 5 5 5 2 2 2 2 2 2 2 2 2 2 2)
:
(de primeFactorz (N)
(use Result
(recur (N)
(let (Root (inc (sqrt N)) X 2)
(when (gt0 (% N X))
(setq X 3)
(while
(and
(gt0 (% N X))
(< (inc 'X 2) Root) ) ) )
(setq
X (if (<= X Root) X N)
Result (cons X Result) )
(unless (= X N) (recurse (/ N X))) ) )
Result ) )
/Lindsay
On Sat, Feb 25, 2017 at 1:25 AM, Joh-Tob Schäg <[email protected]> wrote:
> I verified that it works for all numbers lower than 10000000.
>
>
> My code:
> (let N 2
> (while (> 10000000 N )
> (ifn (= N (apply '* (prime-factors N)))
> (print N))
> (inc 'N)))
>
> 2017-02-25 9:58 GMT+01:00 Alexander Burger <[email protected]>:
>
>> Hi Lindsay, Joh-Tob,
>>
>> On Sat, Feb 25, 2017 at 09:36:04AM +0100, Joh-Tob Schäg wrote:
>> > The purpose of the list is to increase the speed of the algorithm by
>> > skipping some numbers. This is possible because of the math of
>> Differences
>>
>> Correct.
>>
>> > between consecutive primes but i am currently verifying the algorithm
>> if it
>> > works, since the list might be wrong.
>>
>> I took it from Donald E. Knuth's "Art of Computer Programming", Volume 2
>> (Seminumerical Algorithms). In "Factoring into Primes" on page 365 he
>> writes:
>>
>> The sequence ... of trial divisors .. can be taken to be simply 2, 3,
>> 5, 7,
>> 11, 13, 17, 19, 23, 25, 29, 31, 35, .. where we alternately add 2 and
>> 4 after
>> the first three terms.
>> ...
>> A further savings of 20 percent ... removing the numbers 30m +/- 5 ..
>>
>> I believe the term (let (D 2 L (1 2 2 . (4 2 4 2 4 6 2 6 .)) generates
>> that
>> sequence.
>>
>> ♪♫ Alex
>>
>>
>> >
>> > 2017-02-25 7:44 GMT+01:00 Lindsay John Lawrence <
>> > [email protected]>:
>> >
>> > > Does anyone know the algorithm that is being expressed here?
>> > >
>> > > I am trying to understand the code... http://picolisp.com/wiki/?99p35
>> > >
>> > > de prime-factors (N)
>> > > (make
>> > > (let (D 2 L (1 2 2 . (4 2 4 2 4 6 2 6 .)) M (sqrt N))
>> > > (while (>= M D)
>> > > (if (=0 (% N D))
>> > > (setq M (sqrt (setq N (/ N (link D)))))
>> > > (inc 'D (pop 'L)) ) )
>> > > (link N) ) ) )
>> > >
>> > > and having difficulties understanding the purpose of the circular
>> list.
>> > >
>> > > /Lindsay
>> > >
>> > >
>> > >
>> --
>> UNSUBSCRIBE: mailto:[email protected]?subject=Unsubscribe
>>
>
>
