# Re: Fixed-point scaling and lookup tables

Hi,

I finally made a start on these tables... (there has been so much other
stuff to explore with picolisp =)

But I think I may have hit a dead-end right away for a 'pure' picolisp
implementation; from the performance benefit point of view. At least for
the two tables I cared most about.. multiplication and division. An idx,
while impressively fast, comes nowhere near native multiplication.

I'll try a table lookup implementation via a shared lib and see what
overhead the function call would add. The time delta may also disappear for
scientific tables (sin, cos, log, etc).

In the meantime I thought I would share the code below for any thoughts or
observations... demonstrates multiplication by table lookup and addition.

This is the only instance I've run into where I have wanted some kind
explicit array in picolisp...  but I wouldn't trade a bit of the current
functionality and performance of the platform for it.

/Lindsay

#                2          2
# ab = ( ((a + b)  - (a - b)  ) ) / 4
#
#

(let (A (rand 1 255) B (rand 1 255)) (= (* A B) (>> 2 (- (** (abs (+ A B))
2) (** (abs (- A  B)) 2))) ) )

#
# For a restricted integer number range, using a table of 'squares' / 4
# reduces the multiplication to 3 additions (with two table lookups)
#

(let (A (rand 1 255) B (rand 1 255))(= (* A B) (- (cdr (lup *MULTBL (abs (+
A B)))) (cdr (lup *MULTBL (abs (- A B)))))) )

# Table of squares/4
(nil (setq *MULT (make (for N (** 2 9) (link (cons N (>> 2 (* N N )) ))))))
(balance '*MULTBL *MULT)

# Test functions
(de MLup (A B)
(-
(cdr (lup *MULTBL (abs (+ A B))))
(cdr (lup *MULTBL (abs (- A B)))) ) )

# Multiplication by lookup
(de mult-test2 ()
(bench
(do (** 2 20)
(let (
A (rand 1 255)
B (rand 1 255)
A+B (cdr (lup *MULTBL (abs (+ A B))))
A-B (cdr (lup *MULTBL (abs (- A B)))) ) (- A+B A-B) ) ) ) )

# Built-in multiplication
(de mult-test1 ()
(bench
(do (** 2 20)
(let (
A (rand 1 255)
B (rand 1 255) )
(* A B) ) ) ) )

: (mult-test1)
0.392 sec
-> 14151
: (mult-test2)
1.507 sec
-> 2249
: (= (* 13 41) (MLup 13 41))
-> T

2017-04-01 22:45 GMT+02:00 Lindsay John Lawrence <
>> lawrence.lindsayj...@gmail.com>:
>>
>>> My next little picolisp project..
>>>
>>> Picolisp's built-in functions for scaled arithmetic are brilliant once
>>> you understand how they work. Still, it would be great to get more
>>> scientific functions without have to link an external math lib, and get
>>> 'real-time' performance when needed as well.
>>>
>>> http://wilsonminesco.com/16bitMathTables/ is a nice write-up (link
>>> found on hacker news) of what you can do with fixed point, scaling and
>>> lookup tables... Also has links to code to generate the tables.
>>>
>>> I think the concepts and technique will transfer quite nicely to
>>> picolisp.  We'll see...
>>>
>>> /Lindsay
>>>
>>>
>>
>