Re: Fixed-point scaling and lookup tables
Hi Lindsay,
yes, Picolisp has been a great tool for me as well to explore algorithms
and datastructures.
You used the high level implementation of fastNth (took around 15 seconds)
instead of the
low level implementation (it took 3 seconds).
In fact, taken both implementations in isolation (without all that high
level code inside the loop), the low level implementation is 30 times
faster than the high level one on average.
The idx mechanism is a perfect implementation of associative array
functionality when the set of keys is a set of arbitrary strings.
But what happens when the set of keys is a more restricted set like a
sequence of numbers? That is a common scenario and I have seen people
implement that using idx, because Picolisp readily offers that solution.
I think that the Digital Search Tree structure (dst) is the perfect
solution for such a restricted set of keys (array functionality), perfect
in terms of memory space (keys are implicit, not stored), in terms of
execution time (no need to compare keys), and in terms of not needing to
change picolisp internally in order to implement arrays.
A dst complements idx, it does not substitute it.
Here is the code needed to compile the low level implementation of fastNth:
(load "@lib/gcc.l")
(gcc "fast" NIL 'fastNth)
any fastNth(any ex) {
any x = cdr(ex);
int n = (unDig(EVAL(cadr(x)))>>1) - 1;
x = EVAL(car(x));
NeedVar(ex,x);
int i;
int A = 7 & n;
int B = 7 & (n >>= 3);
int C = 7 & (n >>= 3);
int D = 7 & (n >>= 3);
int E = 7 & (n >>= 3);
int F = 7 & (n >>= 3);
int G = (n >> 3);
for (i = 0; i < G; ++i) x = cdr(x); x = car(x);
for (i = 0; i < F; ++i) x = cdr(x); x = car(x);
for (i = 0; i < E; ++i) x = cdr(x); x = car(x);
for (i = 0; i < D; ++i) x = cdr(x); x = car(x);
for (i = 0; i < C; ++i) x = cdr(x); x = car(x);
for (i = 0; i < B; ++i) x = cdr(x); x = car(x);
for (i = 0; i < A; ++i) x = cdr(x);
return x;
}
/**/
the /**/ is an end-delimiter.
Enrique.
Re: Fixed-point scaling and lookup tables
> > For a much faster solution than the idx mechanism, look at this: > http://www.mail-archive.com/picolisp@software-lab.de/msg05199.html > > This is a very interesting idea. Thanks for pointing it out. Is there a formal name for the algorithm? For some more general purpose data structures I am working with, it may be a great solution. I'll compare it to what I was in the process of doing, which was to have an 'idx something to the effect of (N, nth L N). However, for the numerical table lookups, if I am going to a shared lib, I might as well do the ~O(1) lookup in a static array. /Lindsay
Re: Fixed-point scaling and lookup tables
For a much faster solution than the idx mechanism, look at this: http://www.mail-archive.com/picolisp@software-lab.de/msg05199.html It would be nice if Picolisp had this generic fastNth function, in order to solve this kind of lookup accesses. Enrique.
Re: Fixed-point scaling and lookup tables
Hi Lindsay, > 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. True > In the meantime I thought I would share the code below for any thoughts or > observations... demonstrates multiplication by table lookup and addition. Thanks for sharing so far! Looks good :) ♪♫ Alex -- UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe
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 >>> >>> >> >
Re: Fixed-point scaling and lookup tables
>Picolisp's built-in functions for scaled arithmetic are brilliant That's music to my ears because I've been looking forward to working with those ever since I started Picolisp for solving systems of equations. Still working on acquiring the data at the moment but...getting there :), Thank you for the write-up. On 1 April 2017 at 22:20, Joh-Tob Schäg <johtob...@gmail.com> wrote: > I'll wait. > > 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 >> >> >
Re: Fixed-point scaling and lookup tables
I'll wait. 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 > >
Fixed-point scaling and lookup tables
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
