From: ptkwt@... (Phil Tomson)
Date: 2005-06-26T03:25:39+09:00
Subject: Re: [ANN] FixedPt-0.0.1

In article <d9ivki$iu0$1@sea.gmane.org>,
Florian Gro�  <florgro@gmail.com> wrote:
>Phil Tomson wrote:
>
>> What's a fixed point number?
>> -------------------------------------
>> First off  a fixed point number is represented by a limited number of 
>> bits.
>> You can  define that limit when you construct a FixedPt:
>>   fp = FixedPt.new(9.25,6,2)
>
>It's an interesting library and who knows -- I'd not be entirely too 
>surprised if there were use cases out of hardware design for this.
>
>Anyway, I'm writing this because I am wondering if you also allow a 
>String style constructor like FixedPt.new("9.25", 6, 2)? Otherwise you 
>could get a bit of trouble when working with FixedPt numbers with lots 
>of post-decimal digits because the float literal implies a certain 
>inaccurateness.

Constuction with Strings is not currently supported, but that's a 
thought.  Practically speaking, I'm not sure how big of a problem this 
is, I doubt I'd really need to have a FixedPt number with more 
precision than Ruby has.

I did some experimenting in irb to find out where the cutoff is:

irb(main):027:0> x = 9.0000000000001
=> 9.0000000000001
irb(main):028:0> x = 9.00000000000001
=> 9.00000000000001
irb(main):029:0> x = 9.000000000000001
=> 9.0

It happens at 15 digits to the right of the decimal point.  (When you 
go the other way by increasing the size of the number you automatically 
convert to a Bignum - however we don't have a 'Smallnum' equivilent when the 
numbers get very small.)  That would be about 50 fractional bits in a 
binary fixed point number - practically speaking, you usually (where 
'usually' probably covers 99.999% of the cases ) don't need that kind of 
precision in a hardware implementation of an algorithm.  

Mostly, you would use FixedPt to figure out how few fractional bits you 
can get away with before things break.  For example (actual example which 
caused me to develop FixedPt), let's say you need to calculate exp(-x) in 
a function.  Since you want to implement in hardware, often the best way 
to represent a function like exp is to use a lookup table.  Keep in 
mind that the value of exp(-x) is between 0 and 1 (1 when x is 0, '0' for 
all practical purposes when x is large). There are three issues to 
consider when constructing a lookup table for exp(-x):

1) How many bits of precision will I need to accurately represent the 
values I get from the lookup table? (where 'accurately' is dependent on 
how the values will be used.)  This can be determined by experimentation 
in which you try some number of fractional bits and then use the values 
in your algorithm; if it works, keep trying to reduce the number of 
fractional bits till it fails.  Remember, we want to reduce the number of 
bits as much as possible because we're going to implement in real 
hardware where such resources cost $.

2) At what value of x will we consider the output of the function to be 
0.0? 

3) How much resolution should the lookup table have in order to produce 
accurate results in the target algorithm?  In other words, how many 
entries will the lookup table need? (again, this has to be determined 
experimentally)

I implemented a model of a Support Vector Machine (kind of like a 
Perceptron, a type of artificial neuron) using FixedPt and an exp(-x) 
lookup table and came up with the following results:

1) I needed 9 fractional bits at a minimum.
2) The value of x for which exp(-x) = 0.0 was -12.25.
3) The number of entries in the exp(-x) lookup table was 128 (7 bits of 
address) which was surprisingly small.

Phil