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

[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