(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 .
(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
(prime-root (expt 11 20))
Is it a Vlisp BUG ?(rem (expt 11 20) 11) --> 6
(rem (expt 11. 20) 11) --> 7.0
_$ (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))
_$ (primefactors 19683)
((3 9))
_$ (primefactors 19487171)
((11 7))
_$ (primefactors 48828125)
((5 11))
_$ (primefactors 256)
((2 8))
_$ (primefactors 144)
((3 2) (2 4))
(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
Nice code Stefan (as always) 8-)Thank you very much Lee.
An optimisation of Stefan's code:Code - Auto/Visual Lisp: [Select]
Anyway, I still looking for a better method to find the next divisor, since I think my method is highly inefficient.
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 ?
For reasonable integersThanks Stefan , thank you very much .Code - Auto/Visual Lisp: [Select]
) ) ) ) )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))
Nice code Stefan (as always) 8-)1+
Nice code , Lee . Thank you very much .Code - Auto/Visual Lisp: [Select]
i n ) f (* f p) n (/ i f) ) ) l ) ) ) 2 r n ) ) ) r ) ) ) Code: [Select]_$ (primefactors 19683)
((3 9))
_$ (primefactors 19487171)
((11 7))
_$ (primefactors 48828125)
((5 11))
_$ (primefactors 256)
((2 8))
_$ (primefactors 144)
((3 2) (2 4))
this one does not work with 144Thanks VovKa .Code: [Select](defun test (n / a b c)
posting just to demonstrate another approach
(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)
)
(test 18) ;; -->' (18 1) not Prime factor .
_$
;;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"> 加载
_$
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"> 加载
_$
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) :-)
In fact, I often follow with interest about your site .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 (http://lee-mac.com/assocplusplus.html) is a generalisation of the function, if you are interested.
Hi all!The question really is I would like to ask (though my poor english ).
why in the name of the topic has not {Challenge}??
I think I missed the fun...
my versionHi , Evgeniy .Code - Auto/Visual Lisp: [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
Hi , This my test result .
< .. >
Num = 48828125Code: [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"> 加载
_$
I'm sorry to miss the link , I'll add it .Hi , This my test result .
< .. >
Num = 48828125Code: [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
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
_$ (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))
oldCode - Auto/Visual Lisp: [Select]
oldNice code , Evgeniy :-)Code - Auto/Visual Lisp: [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
--------------------------------------------------------------------------------
;;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
--------------------------------------------------------------------------------
_$
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
--------------------------------------------------------------------------------
_$
(ss-test 64 '((SF:pf 399880009) (LM:pf 399880009) (VK:pf 399880009) (SF:pf2 399880009) (eea 399880009)))
_$
测试耗时......毫秒 / 相对速度 ...... 迭代次数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>
_$
(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)
)
oldNice code , Evgeniy :-)Code - Auto/Visual Lisp: [Select]
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 testCode - Auto/Visual Lisp: [Select]
) ) (f n 2 0) )
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
--------------------------------------------------------------------------------
code to compare the speed :-)Code - Auto/Visual Lisp: [Select]
see first post...Code: [Select](Foo 144) --> NIL ;;(expt 12 2) = 144 , But 12 is not Prime Number .
see first post...Code: [Select](Foo 144) --> NIL ;;(expt 12 2) = 144 , But 12 is not Prime Number .
399880009 is my function's favourite number :-PIt's the max powered number in my computer . :-)
(QuickBench (mapcar '(lambda (f) (list f 399880009)) (list SF:pf LM:pf VK:pf SF:pf2 eea eea-2 LM:f2)))
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(QuickBench (mapcar '(lambda (f) (list f 19487171)) (list SF:pf LM:pf VK:pf SF:pf2 SS:pf eea eea-2 LM:f2)))
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
--------------------------------------------------------------------------------
It's the max powered number in my computer . :-)my function will root even bigger numbers i. e. 40000000000 (200000 ^ 2)
New Testi have different results, and i can't understand why...Code: [Select](QuickBench (mapcar '(lambda (f) (list f 399880009)) (list SF:pf LM:pf VK:pf SF:pf2 eea eea-2 LM:f2)))
(QuickBench
(mapcar '(lambda (f) (list f 399880009))
(list VK:pf eea-2 LM:f2)
)
)
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
--------------------------------------------------------------------------------
Command: (vk:pf 399880009)
Hard error occurred ***
internal stack limit reached (simulated)
(defun is-prime (n / foo)it's not 'by VovKa', it's 'by chlh_jd'
;;by VovKa
(defun foo (n try)