Topic: How to find a Integer number's prime root and exponent

[chlh_jd]

Hi All
There is a Ineger number , how to find it's prime root and exponent ?
If function Foo to solve it .

Code: [Select]

(Foo 19683) --> '(3 9) ;;(expt 3 9) = 19683
(Foo 19487171) -->'(11 7) ;; (expt 11 7) = 19487171
(Foo 48828125 ) -->'(5 11) ;; (expt 5 11) = 48828125
(Foo 256) --> '(2 8)  ;; (expt 2 8) = 256
(Foo 144) --> NIL ;;(expt 12 2) = 144 , But 12 is not Prime Number .


[chlh_jd]

my version

Code: [Select]

(defun is-prime (n / foo)
  (defun foo  (n try)
    (if (= n try)
      T
      (if (zerop (rem n try))
nil
(foo n (+ try 1))
)
      )
    )
  (foo n 2)
  )
(defun is-power (num n / foo)
  (setq num (float num))
  (defun foo (num n i)
     (cond ((= num 1)
    i)
   ((> num 1)
    (foo (/ num n) n (1+ i))
    )
   )
    )
  (foo num n 0))
(defun prime-root (num / foo)
  ;; by GSLS(SS) 2012-10-10
  (defun foo (num n / i)
    (cond ((and (= (rem num n) 0)
(is-prime n)
(setq i (is-power num n))
(> i 0))
   (list n i))
  ((<= n num)
   (foo num (1+ n)))))
  (foo num 2)
  )
;;;
(prime-root 19683) ;; --> '(3 9)
(prime-root 19487171) ;; -->'(11 7)
(prime-root 48828125) ;; --> '(5 11)
(prime-root 256) ;; --> (2 8)
(prime-root 144) ;; --> NIL


[chlh_jd]

But somewhat surprisingly, this can not return value ?

Code: [Select]

(prime-root (expt 11 20))
Is it a Vlisp  BUG ?

Code: [Select]

(rem (expt 11 20) 11) --> 6
(rem (expt 11. 20) 11) --> 7.0


[dgorsman]

When you provide a number as "6" to a function, its considered an integer.  If you provide a number as "6.0" its considered a real.  When LISP does math on two integers, the result is typically an integer; when one of the values is a real the result is a real.  Sometimes you need to force values from integers to reals in order to get desired results.

[Stefan]

For reasonable integers

Code - Auto/Visual Lisp: [Select]

1. (defun prime_factors (n / x l old)
2.   (setq x 2)
3.   (while (> n 1)
4.     (if (zerop (rem n x))
5.       (setq n (/ n x)
6.             l (if (setq old (assoc x l))
7.                 (subst (list x (1+ (cadr old))) old l)
8.                 (cons (list x 1) l)
9.                 )
10.             )
11.       (if (> (setq x (if (= x 2) 3 (+ 2 x))) (sqrt n)) (setq x n))
12.       )
13.     )
14.   (reverse l)
15.   )

Code: [Select]

_$ (prime_factors 19683) ->((3 9))
_$ (prime_factors 19487171)->((11 7))
_$ (prime_factors 48828125)->((5 11))
_$ (prime_factors 256)->((2 8))
_$ (prime_factors 144)>((2 4) (3 2))

[Lee Mac]

Code - Auto/Visual Lisp: [Select]

1. (defun primefactors ( n / f i p l )
2.     (setq f 1
3.           i n
4.     )
5.     (while (< f i)
6.         (setq p (lowestprimedivisor n)
7.               f (* f p)
8.               n (/ i f)
9.               l (assoc++ p l)
10.         )
11.     )
12.     l
13. )
14.  
15. (defun assoc++ ( x l / a )
16.     (if (setq a (assoc x l))
17.         (subst (list x (1+ (cadr a))) a l)
18.         (cons  (list x 1) l)
19.     )
20. )
21.  
22. (defun lowestprimedivisor ( n / i r c )
23.     (if (= 0 (rem n 2))
24.         2
25.         (progn
26.             (setq i 1
27.                   r n
28.                   c (fix (1+ (sqrt n)))
29.             )
30.             (while (< (setq i (+ 2 i)) c)
31.                 (if (= 0 (rem n i))
32.                     (setq r i i c)
33.                 )
34.             )
35.             r
36.         )
37.     )
38. )
39.  

Code: [Select]

_$ (primefactors 19683)
((3 9))
_$ (primefactors 19487171)
((11 7))
_$ (primefactors 48828125)
((5 11))
_$ (primefactors 256)
((2 8))
_$ (primefactors 144)
((3 2) (2 4))

[Lee Mac]

Nice code Stefan (as always) 

[VovKa]

this one does not work with 144

Code: [Select]

(defun test (n / a b c)
  (setq a (1+ (fix (/ (log n) (log 2)))))
  (while (setq a (1- a)
       c (expt n (/ 1. a))
       b (fix (+ c 0.5))
       c (not (equal (/ c b) 1 1e-8))
)
  )
  (list b a)
)posting just to demonstrate another approach

[Lee Mac]

An optimisation of Stefan's code:

Code - Auto/Visual Lisp: [Select]

1. (defun prime_factors2 ( n / d l x )
2.     (setq x 2)
3.     (while (< 1 n)
4.         (setq d 0)
5.         (while (zerop (rem n x))
6.             (setq d (1+ d)
7.                   n (/ n x)
8.             )
9.         )
10.         (if (< 0 d)
11.             (setq l (cons (list x d) l))
12.         )
13.         (if (< 1 (sqrt n) (setq x (if (= x 2) 3 (+ 2 x))))
14.             (setq l (cons (list n 1) l)
15.                   n 0
16.             )
17.         )
18.     )
19.     (reverse l)
20. )

[Stefan]

Nice code Stefan (as always) 

Thank you very much Lee.

Looking at your code, I suggest to call lowestprimedivisor with 2 args, in which the second would be the last known divisor.
You don't need to check [again] lower than that, as they are already factorized.

[Stefan]

An optimisation of Stefan's code:

Code - Auto/Visual Lisp: [Select]

1. (defun prime_factors2 ( n / d l x )
2.     (setq x 2)
3.     (while (< 1 n)
4.         (setq d 0)
5.         (while (zerop (rem n x))
6.             (setq d (1+ d)
7.                   n (/ n x)
8.             )
9.         )
10.         (if (< 0 d)
11.             (setq l (cons (list x d) l))
12.         )
13.         (if (< 1 (sqrt n) (setq x (if (= x 2) 3 (+ 2 x))))
14.             (setq l (cons (list n 1) l)
15.                   n 0
16.             )
17.         )
18.     )
19.     (reverse l)
20. )

That make sense, since a multiple divisor  can be found in consecutive steps.
Anyway, I still looking for a better method to find the next divisor, since I think my method is highly inefficient.

[Lee Mac]

Anyway, I still looking for a better method to find the next divisor, since I think my method is highly inefficient.

The problem reduces to finding a sequence of primes... 

[chlh_jd]

When you provide a number as "6" to a function, its considered an integer.  If you provide a number as "6.0" its considered a real.  When LISP does math on two integers, the result is typically an integer; when one of the values is a real the result is a real.  Sometimes you need to force values from integers to reals in order to get desired results.

Thanks dgorsman , I there a way to solve the deviation of expt function ?

[chlh_jd]

For reasonable integers

Code - Auto/Visual Lisp: [Select]

1. (defun prime_factors (n / x l old)
2.   (setq x 2)
3.   (while (> n 1)
4.     (if (zerop (rem n x))
5.       (setq n (/ n x)
6.             l (if (setq old (assoc x l))
7.                 (subst (list x (1+ (cadr old))) old l)
8.                 (cons (list x 1) l)
9.                 )
10.             )
11.       (if (> (setq x (if (= x 2) 3 (+ 2 x))) (sqrt n)) (setq x n))
12.       )
13.     )
14.   (reverse l)
15.   )

Code: [Select]

_$ (prime_factors 19683) ->((3 9))
_$ (prime_factors 19487171)->((11 7))
_$ (prime_factors 48828125)->((5 11))
_$ (prime_factors 256)->((2 8))
_$ (prime_factors 144)>((2 4) (3 2))

Thanks Stefan , thank you very much .

Nice code Stefan (as always) 

1+

[chlh_jd]

Code - Auto/Visual Lisp: [Select]

1. (defun primefactors ( n / f i p l )
2.     (setq f 1
3.           i n
4.     )
5.     (while (< f i)
6.         (setq p (lowestprimedivisor n)
7.               f (* f p)
8.               n (/ i f)
9.               l (assoc++ p l)
10.         )
11.     )
12.     l
13. )
14.  
15. (defun assoc++ ( x l / a )
16.     (if (setq a (assoc x l))
17.         (subst (list x (1+ (cadr a))) a l)
18.         (cons  (list x 1) l)
19.     )
20. )
21.  
22. (defun lowestprimedivisor ( n / i r c )
23.     (if (= 0 (rem n 2))
24.         2
25.         (progn
26.             (setq i 1
27.                   r n
28.                   c (fix (1+ (sqrt n)))
29.             )
30.             (while (< (setq i (+ 2 i)) c)
31.                 (if (= 0 (rem n i))
32.                     (setq r i i c)
33.                 )
34.             )
35.             r
36.         )
37.     )
38. )
39.  

Code: [Select]

_$ (primefactors 19683)
((3 9))
_$ (primefactors 19487171)
((11 7))
_$ (primefactors 48828125)
((5 11))
_$ (primefactors 256)
((2 8))
_$ (primefactors 144)
((3 2) (2 4))

Nice code , Lee . Thank you very much .
This is the second time I saw this function 'Assoc++' is a wonderful application , (First in LM:give_change)

[chlh_jd]

this one does not work with 144

Code: [Select]

(defun test (n / a b c)
  (setq a (1+ (fix (/ (log n) (log 2)))))
  (while (setq a (1- a)
       c (expt n (/ 1. a))
       b (fix (+ c 0.5))
       c (not (equal (/ c b) 1 1e-8))
)
  )
  (list b a)
)posting just to demonstrate another approach

Thanks VovKa .
If num = 18

Code: [Select]

(test 18) ;;  -->' (18 1) not Prime factor . 


[chlh_jd]

Hi , This my test result .

Num = 19487171

Code: [Select]

_$
;;QuickBench function see here http://www.theswamp.org/index.php?action=dlattach;topic=42091.0;attach=22832
Benchmarking ..... done for 32768 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(#<USUBR @000000002d519ef8 SF:PF2> 1...)     32768      1840      1840      2.05
(#<USUBR @000000002d519d68 SF:PF> 19...)     16384      1061      2122      1.78
(#<USUBR @000000002d519d18 SS:PF> 19...)     16384      1310      2620      1.44
(#<USUBR @000000002d519db8 VK:PF> 19...)     16384      1701      3402      1.11
(#<USUBR @000000002d519e08 LM:PF> 19...)     16384      1887      3774      1.00
--------------------------------------------------------------------------------
; 11 表格 从 #<editor "C:/Users/CLH/Desktop/prime-root.LSP"> 加载
_$

Num = 48828125

Code: [Select]

Benchmarking ..... done for 32768 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(#<USUBR @000000002d519368 SF:PF2> 4...)     32768      1778      1778      2.35
(#<USUBR @000000002d519188 SS:PF> 48...)     16384      1093      2186      1.91
(#<USUBR @000000002d5191d8 SF:PF> 48...)     16384      1216      2432      1.72
(#<USUBR @000000002d519228 VK:PF> 48...)     16384      1341      2682      1.56
(#<USUBR @000000002d519278 LM:PF> 48...)      8192      1046      4184      1.00
--------------------------------------------------------------------------------
; 11 表格 从 #<editor "C:/Users/CLH/Desktop/prime-root.LSP"> 加载
_$


[Lee Mac]

Nice code , Lee . Thank you very much .
This is the second time I saw this function 'Assoc++' is a wonderful application , (First in LM:give_change)

Thank you - though the performance of my function pales in comparison to Stefan's code, since my more 'modular' approach is repeatedly iterating over previously factorised primes as noted above...

The 'assoc++' function is very useful indeed, I've utilised this construct in many of my applications - here is a generalisation of the function, if you are interested.

[ElpanovEvgeniy]

Hi all!

why in the name of the topic has not {Challenge}??
I think I missed the fun...

[chlh_jd]

Nice code , Lee . Thank you very much .
This is the second time I saw this function 'Assoc++' is a wonderful application , (First in LM:give_change)

Thank you - though the performance of my function pales in comparison to Stefan's code, since my more 'modular' approach is repeatedly iterating over previously factorised primes as noted above...

The 'assoc++' function is very useful indeed, I've utilised this construct in many of my applications - here is a generalisation of the function, if you are interested.

In fact, I often follow with interest  about your site .
I'm sorry to have not been any traces , And thank you again .

[chlh_jd]

Hi all!
why in the name of the topic has not {Challenge}??
I think I missed the fun...

The question really is I would like to ask (though my poor english ).
I've been looking forward to your wonderful code 

[ElpanovEvgeniy]

my version

Code - Auto/Visual Lisp: [Select]

1. (defun eea (n)
2.   (defun f (n x y)
3.     (cond ((or (> 1 n)(> x n)) nil)
4.           ((zerop (rem n x)) (f (/ n x) x (1+ y)))
5.           ((> y 0) (cons (list x y) (f n 2 0)))
6.           ((f n (+ 1 x (rem x 2)) 0))
7.     )
8.   )
9.   (f n 2 0)
10. )

[chlh_jd]

my version

Code - Auto/Visual Lisp: [Select]

1. (defun eea (n)
2.   (defun f (n x y)
3.     (cond ((or (> 1 n)(> x n)) nil)
4.           ((zerop (rem n x)) (f (/ n x) x (1+ y)))
5.           ((> y 0) (cons (list x y) (f n 2 0)))
6.           ((f n (+ 1 x (rem x 2)) 0))
7.     )
8.   )
9.   (f n 2 0)
10. )

Hi , Evgeniy .
Yours can't seem to get rigtht result (prime-root and it's exponent , or named prime factors) .

Code: [Select]

(eea 19683) ;; --> NIL      must '(3 9)
(eea 19487171) ;; -->NIL  must '(11 7)
(eea 48828125) ;; -->NIL  must  '(5 11)
(eea 256) ;; --> NIL          must  '(2 8)
(eea 144) ;; --> NIL         must NIL 
(eea 18) ;; --> '((2 4))     must 'NIL


[Kerry]

Hi , This my test result .
< .. >
Num = 48828125

Code: [Select]

Benchmarking ..... done for 32768 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(#<USUBR @000000002d519368 SF:PF2> 4...)     32768      1778      1778      2.35
(#<USUBR @000000002d519188 SS:PF> 48...)     16384      1093      2186      1.91
(#<USUBR @000000002d5191d8 SF:PF> 48...)     16384      1216      2432      1.72
(#<USUBR @000000002d519228 VK:PF> 48...)     16384      1341      2682      1.56
(#<USUBR @000000002d519278 LM:PF> 48...)      8192      1046      4184      1.00
--------------------------------------------------------------------------------
; 11 表格 从 #<editor "C:/Users/CLH/Desktop/prime-root.LSP"> 加载
_$


chlh_jd,
I can't understand your presentation of processing times.
Can you please post or link to your code.

Note: personally I use a modified verson of MP's Benchmark program.
I've modified Michaels build so that the fastest version is base 1.0 and other times are relative to that.
ie:
if the fastest takes 1000 and the slowest takes 4100 then the relative time is 1.0 for the fastest and 4.1 for the slowest ... so the relative ratio represents the longer processing time.
...  the slowest takes 4.1 times as long to process.

Regards
 

[chlh_jd]

Hi , This my test result .
< .. >
Num = 48828125

Code: [Select]

Benchmarking ..... done for 32768 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(#<USUBR @000000002d519368 SF:PF2> 4...)     32768      1778      1778      2.35
(#<USUBR @000000002d519188 SS:PF> 48...)     16384      1093      2186      1.91
(#<USUBR @000000002d5191d8 SF:PF> 48...)     16384      1216      2432      1.72
(#<USUBR @000000002d519228 VK:PF> 48...)     16384      1341      2682      1.56
(#<USUBR @000000002d519278 LM:PF> 48...)      8192      1046      4184      1.00
--------------------------------------------------------------------------------
; 11 表格 从 #<editor "C:/Users/CLH/Desktop/prime-root.LSP"> 加载
_$


chlh_jd,
I can't understand your presentation of processing times.
Can you please post or link to your code.

Note: personally I use a modified verson of MP's Benchmark program.
I've modified Michaels build so that the fastest version is base 1.0 and other times are relative to that.
ie:
if the fastest takes 1000 and the slowest takes 4100 then the relative time is 1.0 for the fastest and 4.1 for the slowest ... so the relative ratio represents the longer processing time.
...  the slowest takes 4.1 times as long to process.

Regards

I'm sorry to miss the link , I'll add it .
Thanks Kerry for notice , This function QuickBench From theswamp, I have not changed anything .
http://www.theswamp.org/index.php?action=dlattach;topic=42091.0;attach=22832
Can you send your comparison function, thanks a lot .

[ElpanovEvgeniy]

I'm sorry, the first time was not accurate ...

Code - Auto/Visual Lisp: [Select]

1. (defun eea (n)
2.   (defun f (n x y)
3.     (cond ((= n 1) (list x y))
4.           ((zerop (rem n x)) (f (/ n x) x (1+ y)))
5.           ((or (> x n)(and (> y 0) (f n 2 0))) nil)
6.           ((f n (+ 1 x (rem x 2)) 0))
7.     )
8.   )
9.   (f n 2 0)
10. )

[Lee Mac]

Code: [Select]

(eea 19683) ;; --> NIL      must '(3 9)
(eea 19487171) ;; -->NIL  must '(11 7)
(eea 48828125) ;; -->NIL  must  '(5 11)
(eea 256) ;; --> NIL          must  '(2 8)
(eea 144) ;; --> NIL         must NIL 
(eea 18) ;; --> '((2 4))     must 'NIL


I thought you were looking for the prime factorisation... i.e.

Code: [Select]

_$ (prime_factors2 19683)
((3 9))
_$ (prime_factors2 19487171)
((11 7))
_$ (prime_factors2 48828125)
((5 11))
_$ (prime_factors2 256)
((2 8))
_$ (prime_factors2 144)
((2 4) (3 2))
_$ (prime_factors2 18)
((2 1) (3 2))
Or have I misunderstood the task?

[ribarm]

If you checked first (eea n), you'll see that later he omitted some good lines :

Code - Auto/Visual Lisp: [Select]

1. (defun primefactors-eea ( n )
2.   (defun f ( n x y )
3. ;    (cond ((= n 1) (list x y))
4.     (cond ((= n 1) (list (list x y)))
5.           ((zerop (rem n x)) (f (/ n x) x (1+ y)))
6. ;          ((or (> x n)(and (> y 0) (f n 2 0))) nil)
7.           ((> y 0) (cons (list x y) (f n 2 0)))
8.           ((f n (+ 1 x (rem x 2)) 0))
9.     )
10.   )
11.   (f n 2 0)
12. )
13.  

But it can't do recursion for large numbers like 9876543210 and yours Lee can...

[ElpanovEvgeniy]

old

Code - Auto/Visual Lisp: [Select]

1. (defun eea (n)
2.   (defun f (n x y)
3.     (cond ((> 1 n) nil)
4.           ((zerop (rem n x)) (f (/ n x) x (1+ y)))
5.           ((> y 0) (cons (list x y) (f n 2 0)))
6.           ((> x n) nil)
7.           ((f n (+ 1 x (rem x 2)) 0))
8.     )
9.   )
10.   (f n 2 0)
11. )

[Lee Mac]

old

Code - Auto/Visual Lisp: [Select]

1. (defun eea (n)
2.   (defun f (n x y)
3.     (cond ((> 1 n) nil)
4.           ((zerop (rem n x)) (f (/ n x) x (1+ y)))
5.           ((> y 0) (cons (list x y) (f n 2 0)))
6.           ((> x n) nil)
7.           ((f n (+ 1 x (rem x 2)) 0))
8.     )
9.   )
10.   (f n 2 0)
11. )

Code - Auto/Visual Lisp: [Select]

1. ((> y 0) (cons (list x y) (f n 2 0)))

Could become:

Code - Auto/Visual Lisp: [Select]

1. ((> y 0) (cons (list x y) (f n x 0)))

Since all factors less than x have already been factored out.

Nice code

[chlh_jd]

old

Code - Auto/Visual Lisp: [Select]

1. (defun eea (n)
2.   (defun f (n x y)
3.     (cond ((> 1 n) nil)
4.           ((zerop (rem n x)) (f (/ n x) x (1+ y)))
5.           ((> y 0) (cons (list x y) (f n 2 0)))
6.           ((> x n) nil)
7.           ((f n (+ 1 x (rem x 2)) 0))
8.     )
9.   )
10.   (f n 2 0)
11. )

Nice code , Evgeniy 
Thanks Lee Mac and ribarm for your participation .

Hi Evgeniy , After I see  your first version , It's so Concise . so I change it and test

Code - Auto/Visual Lisp: [Select]

1. (defun eea (n / f)
2.   (defun f (n x y)
3.     (cond ((and (> y 0) (zerop (1- n))) (list x y))
4.           ((zerop (rem n x)) (f (/ n x) x (1+ y)))
5.           ((and (> (rem n x) 0) (> y 0)) nil)
6.           ((< 1 (sqrt n) x) (list n 1))  
7.           ((f n (+ 1 x (rem x 2)) 0))
8.     )
9.   )
10.   (f n 2 0)
11. )
12.  

Now , Test efficiency of  All functions , I don't sure the Quickbench function is correct ( If like Kerry said it perhaps must be improve some . )

Code: [Select]

;;Quickbench copy from http://www.theswamp.org/index.php?action=dlattach;topic=42091.0;attach=22832
(QuickBench (mapcar '(lambda (f) (list f 19487171)) (list SF:pf LM:pf VK:pf SF:pf2 SS:pf  eea)))
;;
Benchmarking ...... done for 32768 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(#<USUBR @000000002a1e7ea8 SF:PF2> 1...)     32768      1950      1950      1.95
(#<USUBR @000000002a0b3480 SS:PF> 19...)     16384      1060      2120      1.80
(#<USUBR @000000002a2ca200 EEA> 1948...)     16384      1092      2184      1.74
(#<USUBR @000000002a1e74f8 SF:PF> 19...)     16384      1107      2214      1.72
(#<USUBR @000000002a1e75e8 VK:PF> 19...)     16384      1639      3278      1.16
(#<USUBR @000000002a1e7728 LM:PF> 19...)     16384      1904      3808      1.00
--------------------------------------------------------------------------------


Code: [Select]

;;Quickbench copy from http://www.theswamp.org/index.php?action=dlattach;topic=42091.0;attach=22832
;;
(QuickBench (mapcar '(lambda (f) (list f 48828125)) (list SF:pf LM:pf VK:pf SF:pf2 SS:pf  eea)))
;;
Benchmarking ...... done for 32768 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(#<USUBR @000000002a0b3480 SS:PF> 48...)     32768      1701      1701      2.57
(#<USUBR @000000002a1e7ea8 SF:PF2> 4...)     32768      1842      1842      2.37
(#<USUBR @000000002a2ca200 EEA> 4882...)     16384      1061      2122      2.06
(#<USUBR @000000002a1e74f8 SF:PF> 48...)     16384      1248      2496      1.75
(#<USUBR @000000002a1e75e8 VK:PF> 48...)     16384      1450      2900      1.50
(#<USUBR @000000002a1e7728 LM:PF> 48...)      8192      1091      4364      1.00
--------------------------------------------------------------------------------


[chlh_jd]

I think this condition as Lee Mac OPT Setfan's (< 1 (sqrt n) (setq x (if (= x 2) 3 (+ 2 x)))) reduce a lot of calculation .
 

[chlh_jd]

If test number is 399880009 , mine didn't get the result . another test for 399880009
It's a very different results

Code: [Select]

_$
Benchmarking ..... done for 128 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(#<USUBR @000000002a1e7728 LM:PF> 39...)       128      1436      1436      2.37
(#<USUBR @000000002a1e75e8 VK:PF> 39...)        64      1106      2212      1.54
(#<USUBR @000000002a1e74f8 SF:PF> 39...)        64      1325      2650      1.28
(#<USUBR @000000002a2ca200 EEA> 3998...)        64      1575      3150      1.08
(#<USUBR @000000002a1e7ea8 SF:PF2> 3...)        64      1702      3404      1.00
--------------------------------------------------------------------------------
 
_$

Use my test function result

Code: [Select]

(ss-test 64 '((SF:pf 399880009) (LM:pf 399880009) (VK:pf 399880009) (SF:pf2 399880009) (eea 399880009)))


Code: [Select]

_$

测试耗时......毫秒 / 相对速度 ...... 迭代次数64...:
 LM:PF......359 / 2.39......<Fastest>
 VK:PF......562 / 1.53......
 SF:PF......702 / 1.22......
 EEA......796 / 1.08......
 SF:PF2......858 / 1.00......<Slowest>
_$


Code: [Select]

(defun ss-test (ti funlist / t1 t2 tilst ilst i)
  ;;时间测试函数,funlist 格式为 ((test1 arg) (test2 arg) (test3 arg))
  ;;GSLS(SS) 2011-5-21
  (foreach funname funlist
    (gc)
    (setq t1 (getvar "MilliSecs"))
    (repeat ti
      (vl-catch-all-apply
(car funname)
(cdr funname)
      )
    )
    (setq t2 (getvar "MilliSecs")
  tilst (append tilst (list(- t2 t1)))
  )
  )
  (setq ilst (vl-sort-i tilst (function <)))
  (princ (strcat "\n测试耗时......毫秒 / 相对速度 ...... 迭代次数" (rtos ti 2 0) "...:"))
  (foreach i ilst
    (princ (strcat "\n "
   (vl-prin1-to-string
     (car (nth i funlist))
     )
     "......"      
     (rtos (nth i tilst) 2 0)
     " / "
     (rtos (/ (nth (last ilst) tilst) (nth i tilst)) 2 2)
     "......"
   (cond ((= i (car ilst)) "<Fastest>")
((= i (last ilst)) "<Slowest>")
(t ""))
   )
   )
    ) 
  (princ)
)


[Lee Mac]

Code - Auto/Visual Lisp: [Select]

1. (defun LM:PF3 ( n / d l x )
2.     (setq d 0)
3.     (while (zerop (rem n 2))
4.         (setq d (1+ d)
5.               n (/ n 2)
6.         )
7.     )
8.     (if (< 0 d)
9.         (setq l (cons (list 2 d) l))
10.     )
11.     (setq x 3)
12.     (while (< 1 n)
13.         (while (/= 0 (rem n x))
14.             (setq x (+ x 2))
15.         )
16.         (setq d 0)
17.         (while (zerop (rem n x))
18.             (setq d (1+ d)
19.                   n (/ n x)
20.             )
21.         )
22.         (setq l (cons (list x d) l))
23.     )
24.     (reverse l)
25. )

 

[ElpanovEvgeniy]

old

Code - Auto/Visual Lisp: [Select]

1. (defun eea (n)
2.   (defun f (n x y)
3.     (cond ((> 1 n) nil)
4.           ((zerop (rem n x)) (f (/ n x) x (1+ y)))
5.           ((> y 0) (cons (list x y) (f n 2 0)))
6.           ((> x n) nil)
7.           ((f n (+ 1 x (rem x 2)) 0))
8.     )
9.   )
10.   (f n 2 0)
11. )

Nice code , Evgeniy 
Thanks Lee Mac and ribarm for your participation .

Hi Evgeniy , After I see  your first version , It's so Concise . so I change it and test

Code - Auto/Visual Lisp: [Select]

1. (defun eea (n / f)
2.   (defun f (n x y)
3.     (cond ((and (> y 0) (zerop (1- n))) (list x y))
4.           ((zerop (rem n x)) (f (/ n x) x (1+ y)))
5.           ((and (> (rem n x) 0) (> y 0)) nil)
6.           ((< 1 (sqrt n) x) (list n 1))  
7.           ((f n (+ 1 x (rem x 2)) 0))
8.     )
9.   )
10.   (f n 2 0)
11. )
12.  

Now , Test efficiency of  All functions , I don't sure the Quickbench function is correct ( If like Kerry said it perhaps must be improve some . )

Code: [Select]

;;Quickbench copy from http://www.theswamp.org/index.php?action=dlattach;topic=42091.0;attach=22832
(QuickBench (mapcar '(lambda (f) (list f 19487171)) (list SF:pf LM:pf VK:pf SF:pf2 SS:pf  eea)))
;;
Benchmarking ...... done for 32768 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(#<USUBR @000000002a1e7ea8 SF:PF2> 1...)     32768      1950      1950      1.95
(#<USUBR @000000002a0b3480 SS:PF> 19...)     16384      1060      2120      1.80
(#<USUBR @000000002a2ca200 EEA> 1948...)     16384      1092      2184      1.74
(#<USUBR @000000002a1e74f8 SF:PF> 19...)     16384      1107      2214      1.72
(#<USUBR @000000002a1e75e8 VK:PF> 19...)     16384      1639      3278      1.16
(#<USUBR @000000002a1e7728 LM:PF> 19...)     16384      1904      3808      1.00
--------------------------------------------------------------------------------


Code: [Select]

;;Quickbench copy from http://www.theswamp.org/index.php?action=dlattach;topic=42091.0;attach=22832
;;
(QuickBench (mapcar '(lambda (f) (list f 48828125)) (list SF:pf LM:pf VK:pf SF:pf2 SS:pf  eea)))
;;
Benchmarking ...... done for 32768 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(#<USUBR @000000002a0b3480 SS:PF> 48...)     32768      1701      1701      2.57
(#<USUBR @000000002a1e7ea8 SF:PF2> 4...)     32768      1842      1842      2.37
(#<USUBR @000000002a2ca200 EEA> 4882...)     16384      1061      2122      2.06
(#<USUBR @000000002a1e74f8 SF:PF> 48...)     16384      1248      2496      1.75
(#<USUBR @000000002a1e75e8 VK:PF> 48...)     16384      1450      2900      1.50
(#<USUBR @000000002a1e7728 LM:PF> 48...)      8192      1091      4364      1.00
--------------------------------------------------------------------------------


why fix my code?

Code - Auto/Visual Lisp: [Select]

1. (defun eea-edit-chlh_jd (n / f)
2.   (defun f (n x y)
3.     (cond ((and (> y 0) (zerop (1- n))) (list x y))
4.           ((zerop (rem n x)) (f (/ n x) x (1+ y)))
5.           ((and (> (rem n x) 0) (> y 0)) nil)
6.           ((< 1 (sqrt n) x) (list n 1))
7.           ((f n (+ 1 x (rem x 2)) 0))
8.     )
9.   )
10.   (f n 2 0)
11. )
12. (defun eea (n)
13.   (defun f (n x y)
14.     (cond ((> 1 n) nil)
15.           ((zerop (rem n x)) (f (/ n x) x (1+ y)))
16.           ((> y 0) (cons (list x y) (f n 2 0)))
17.           ((> x n) nil)
18.           ((f n (+ 1 x (rem x 2)) 0))
19.     )
20.   )
21.   (f n 2 0)
22. )

Code - Auto/Visual Lisp: [Select]

1. (BenchMark '((eea 399880009)(eea-edit-chlh_jd 399880009)))

Code - Auto/Visual Lisp: [Select]

1. Benchmarking .........Elapsed milliseconds / relative speed for 64 iteration(s):
2.  
3.     (EEA 399880009)..................1264 / 1.42 <fastest>
4.     (EEA-EDIT-CHLH_JD 399880009).....1794 / 1 <slowest>
5.  

[ElpanovEvgeniy]

code to compare the speed 

Code - Auto/Visual Lisp: [Select]

1. (defun eea-2 (n / x y)
2.   (setq x 2 y 0)
3.   (while (and (< x n) (< 0 (rem n x)))
4.     (setq x (+ 1 x (rem x 2)))
5.   )
6.   (while (= 0 (rem n x))
7.     (setq n (/ n x) y (1+ y))
8.   )
9.   (if (= 1 n)
10.     (list x y)
11.   )
12. )

[Lee Mac]

code to compare the speed 

Code - Auto/Visual Lisp: [Select]

1. (defun eea-2 (n / x y)
2.   (setq x 2 y 0)
3.   (while (and (< x n) (< 0 (rem n x)))
4.     (setq x (+ 1 x (rem x 2)))
5.   )
6.   (while (= 0 (rem n x))
7.     (setq n (/ n x) y (1+ y))
8.   )
9.   (if (= 1 n)
10.     (list x y)
11.   )
12. )

Code - Auto/Visual Lisp: [Select]

1. _$ (eea-2 18)
2. nil
3. _$ (LM:PF3 18)
4. ((2 1) (3 2))

We are not comparing apples with apples...

[ElpanovEvgeniy]

Code: [Select]

(Foo 144) --> NIL ;;(expt 12 2) = 144 , But 12 is not Prime Number .


see first post...

[Lee Mac]

Code: [Select]

(Foo 144) --> NIL ;;(expt 12 2) = 144 , But 12 is not Prime Number .


see first post...

In that case:

Code - Auto/Visual Lisp: [Select]

1. (defun f ( n / d x )
2.     (if (zerop (rem n 2))
3.         (setq x 2)
4.         (progn
5.             (setq x 3)
6.             (while (< 0 (rem n x)) (setq x (+ x 2)))
7.         )
8.     )
9.     (setq d 0)
10.     (while (zerop (rem n x)) (setq n (/ n x) d (1+ d)))
11.     (if (= 1 n)
12.         (list x d)
13.     )
14. )

[VovKa]

399880009 is my function's favourite number 

[chlh_jd]

Hi Evgeniy ,
Hi Lee Mac ,
I'm sorry for my poor english .
In my first post , I supposed the condition : the number only one factor , the number 144 has two factors so it return nil .

399880009 is my function's favourite number 

It's the max powered number  in my computer .

[chlh_jd]

New Test

Code: [Select]

(QuickBench (mapcar '(lambda (f) (list f 399880009)) (list SF:pf LM:pf VK:pf SF:pf2  eea eea-2 LM:f2)))


Code: [Select]

Benchmarking ....... done for 128 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(#<USUBR @000000002a4aab10 LM:F2> 39...)       128      1077      1077      3.22
(#<USUBR @000000002a4aa1d8 LM:PF> 39...)       128      1388      1388      2.50
(#<USUBR @000000002a620a20 EEA-2> 39...)       128      1902      1902      1.82
(#<USUBR @000000002a3c7b38 VK:PF> 39...)        64      1107      2214      1.56
(#<USUBR @000000002a3c75e8 SF:PF> 39...)        64      1358      2716      1.28
(#<USUBR @000000002a6207a0 EEA> 3998...)        64      1560      3120      1.11
(#<USUBR @000000002a6203e0 SF:PF2> 3...)        64      1732      3464      1.00
--------------------------------------------------------------------------------
For 19487171

Code: [Select]

(QuickBench (mapcar '(lambda (f) (list f 19487171)) (list SF:pf LM:pf VK:pf SF:pf2 SS:pf  eea eea-2 LM:f2)))


Code: [Select]

Benchmarking ........ done for 32768 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(#<USUBR @000000002a4aab10 LM:F2> 19...)     32768      1482      1482      2.55
(#<USUBR @000000002a620a20 EEA-2> 19...)     32768      1592      1592      2.37
(#<USUBR @000000002a6203e0 SF:PF2> 1...)     32768      1887      1887      2.00
(#<USUBR @0000000029f2c638 SS:PF> 19...)     32768      2011      2011      1.88
(#<USUBR @000000002a3c75e8 SF:PF> 19...)     16384      1044      2088      1.81
(#<USUBR @000000002a6207a0 EEA> 1948...)     16384      1046      2092      1.80
(#<USUBR @000000002a3c7b38 VK:PF> 19...)     16384      1638      3276      1.15
(#<USUBR @000000002a4aa1d8 LM:PF> 19...)     16384      1887      3774      1.00
--------------------------------------------------------------------------------


[VovKa]

It's the max powered number  in my computer .

my function will root even bigger numbers i. e. 40000000000 (200000 ^ 2)

New Test

Code: [Select]

(QuickBench (mapcar '(lambda (f) (list f 399880009)) (list SF:pf LM:pf VK:pf SF:pf2  eea eea-2 LM:f2)))


i have different results, and i can't understand why...

Code: [Select]

(QuickBench
  (mapcar '(lambda (f) (list f 399880009))
  (list VK:pf eea-2 LM:f2)
  )
)

Code: [Select]

Benchmarking ... done for 4096 iterations. Sorted from fastest.
Statement                                Increment  Time(ms) Normalize  Relative
--------------------------------------------------------------------------------
(#<USUBR @0822a9c4 VK:PF> 399880009)          4096      1080      1080    136.89
(#<USUBR @0822ad0c LM:F2> 399880009)            64      1313     84032      1.76
(#<USUBR @0822ace4 EEA-2> 399880009)            32      1155    147840      1.00
--------------------------------------------------------------------------------

[Kerry]

Vovka, your routine

Code - Auto/Visual Lisp: [Select]

1.  (vk:pf 399880009)

blows up my computer
with acad2013 64 win 7 pro

Command: (vk:pf 399880009)
Hard error occurred ***
internal stack limit reached (simulated)

However, if I use 48828125 I get this result

Code - Auto/Visual Lisp: [Select]

1. (defun vk:pf (n / a b c)
2.   ;;by VovKa
3.   (setq a (1+ (fix (/ (log n) (log 2)))))
4.   (while (setq a (1- a)
5.                c (expt n (/ 1. a))
6.                b (fix (+ c 0.5))
7.                c (not (equal (/ c b) 1 1e-8))
8.          )
9.   )
10.   (if (is-prime b)
11.     (list b a)
12.   ) ;_add is-prime
13. )
14. (defun is-prime (n / foo)
15.   ;;by VovKa
16.   (defun foo (n try)
17.     (if (= n try)
18.       t
19.       (if (zerop (rem n try))
20.         nil
21.         (foo n (+ try 1))
22.       )
23.     )
24.   )
25.   (foo n 2)
26. )
27.  
28.  
29. (defun eea-2 (n / x y)
30.   ;; ElpanovEvgeniy http://www.theswamp.org/index.php?topic=42965.msg482261#msg482261
31.   (setq x 2
32.         y 0
33.   )
34.   (while (and (< x n) (< 0 (rem n x)))
35.     (setq x (+ 1 x (rem x 2)))
36.   )
37.   (while (= 0 (rem n x))
38.     (setq n (/ n x)
39.           y (1+ y)
40.     )
41.   )
42.   (if (= 1 n)
43.     (list x y)
44.   )
45. )
46.  
47. (defun lm:f2 (n / d x)
48.   ;; LM  http://www.theswamp.org/index.php?topic=42965.msg482268#msg482268
49.   (if (zerop (rem n 2))
50.     (setq x 2)
51.     (progn (setq x 3)
52.            (while (< 0 (rem n x)) (setq x (+ x 2)))
53.     )
54.   )
55.   (setq d 0)
56.   (while (zerop (rem n x))
57.     (setq n (/ n x)
58.           d (1+ d)
59.     )
60.   )
61.   (if (= 1 n)
62.     (list x d)
63.   )
64. )

Code - Auto/Visual Lisp: [Select]

1. (benchmark
2.   '((vk:pf 48828125)
3.     (eea-2 48828125)
4.     (lm:f2 48828125))
5. )

Code - Auto/Visual Lisp: [Select]

1. Benchmarking [M.P. 2005 < revised kdub 2005>] ................
2. Elapsed milliseconds for 8192 iteration(s)/ relative Timing :
3.  
4.     (VK:PF 48828125).....375 / 1.7202 <slowest>
5.     (EEA-2 48828125).....219 / 1.0046
6.     (LM:F2 48828125).....218 / 1 <fastest>

I assume that those versions are correct
Regards

[VovKa]

(defun is-prime   (n / foo)
  ;;by VovKa
  (defun foo (n try)

it's not 'by VovKa', it's 'by chlh_jd'

anyway my function should not be benchmarked along with others because it doesn't work as supposed

[chlh_jd]

Hi Kerry , Thanks you for participation .
As VovKa said , in the 'prime-root.lsp' I post , 'is-prime' function is my poor code .
Hi VovKa , If didn't add this function ,  yours can't get the result I want , only for prime number Or only one factor .