Hi Enrique,
> I like a lot what you are doing with fixed point scaling and lookup tables.
Thank you.
PicoLisp has been a great tool for me to explore algorithms and data
with the past few months.
> The formal name of the algorithm coded in the fastNth primitive is Digital
> Tree Searching, a special case of Radix Searching.
In the implementation below, it appears to be 1/2 again as slow as an
idx. (not shown, but runs in ~10secs)
So, not so useful for multiplication. It is faster than built-in nth
on large arrays and uses less resources then idx here.
/Lindsay
# Code
: (nil (let (Cnt 0) (setq *A (make (for N (** 2 16) (link (>> 2 (* Cnt
Cnt))) (inc 'Cnt))))))
: (nil (setq *B (helper *A)))
(de leap (L)
(make
(for (P L P (nth P 9))
(link P) ) ) )
(de helper (L)
(leap (leap (leap (leap (leap (leap L)))))) )
(de fastNth (L N)
(let
(A (& 7 N)
B (& 7 (setq N (>> 3 N)))
C (& 7 (setq N (>> 3 N)))
D (& 7 (setq N (>> 3 N)))
E (& 7 (setq N (>> 3 N)))
F (& 7 (setq N (>> 3 N)))
G (>> 3 N) )
(nth
L
(inc G)
(inc F)
(inc E)
(inc D)
(inc C)
(inc B)
(inc A) ) ) )
(de MFast (A B)
(-
(car (fastNth *B (abs (+ A B))))
(car (fastNth *B (abs (- A B)))) ) )
(de mult-test3 NIL
(bench
(do (** 2 24)
(let
(A (rand 1 65536)
B (rand 1 65536)
A+B (car (fastNth *B (abs (+ A B))))
A-B (car (fastNth *B (abs (- A B)))) )
(- A+B A-B) ) ) ) )
(de mult-test1 NIL
(bench
(do (** 2 24)
(let (A (rand 1 65536) B (rand 1 65536))
(* A B) ) ) ) )
: (mult-test1)
1.078 sec
-> 48625344
: (mult-test3)
14.717 sec
-> NIL
--
UNSUBSCRIBE: mailto:[email protected]?subject=Unsubscribe
