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:picolisp@software-lab.de?subject=Unsubscribe

Reply via email to