Re: Fixed-point scaling and lookup tables
Hi Lindsay, I like a lot what you are doing with fixed point scaling and lookup tables. It reminds me of programming in the Forth language, years ago. The formal name of the algorithm coded in the fastNth primitive is Digital Tree Searching, a special case of Radix Searching. The algorithm is the same as that for Binary Tree Searching, except that we branch in the tree not according to the result of the comparison between keys (as idx does), but according to the key's bits. Because of the unavoidable lisp virtual machine overhead, a C primitive that searches this Digital Tree is almost as fast as a C primitive that just uses an static array in C. This is not the case with idx, as the comparison of keys that it makes at each level is expensive. But idx can be used for many more things, a digital tree seems to be a specialized tool. No need to use shared libs, as the fastNth primitive is general enough to handle any big array. Enrique.
Subscribe
Hello Karl-Heinz Kreis :-) You are now subscribed -- UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe
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
