0

I am implementing fixed point arithmetic using the slides [1]. Everything is working as it should my question is the slides linked, also every resource I read says when multiplying and dividing fixed point numbers there is a good change they overflow. So they suggest casting them to a bigger size to multiply then cast back. Like,

(INT32)(((INT64)a *
        (INT64)b) >> N)

instead of just,

 ((a * b) >> N)

This works for 8,16,32 bit integers but how do I handle overflow for 64 bit integer? There is no 128 bit int type (AFAIK gcc has 128 bit integers but they are not portable.)

I also would like to via the constructor auto calculate required bits for the user supplied epsilon (minimum required fraction accuracy) Like so,

If 0.01 accuracy is required 6 bits is enough for N. (Since 1/64 = 0.015) I couldn't figure out the logic for converting accuracy to required bits?

[1] http://jet.ro/files/The_neglected_art_of_Fixed_Point_arithmetic_20060913.pdf

Hamza Yerlikaya
  • 49,047
  • 44
  • 147
  • 241
  • To convert accuracy to required bits you can use a simple math formula. `floor(log(1.0/required_accuracy)/log(2))` – Sanket Makani Jun 11 '17 at 17:45
  • Implement [long multiplication](https://en.wikipedia.org/wiki/Multiplication_algorithm#Long_multiplication). Recall how, in elementary school, you could multiply two-digit decimal numbers using only single-digit multiplication table. – Igor Tandetnik Jun 11 '17 at 18:06
  • Long multiplication, as Igor says... but 64-bit fixed-point is not very useful so you probably don't need to bother with it. – Matt Timmermans Jun 11 '17 at 21:34

1 Answers1

0

well you can chain 64 bit ops to produce N*64 bit operations. With +,- it is simple O(n) stacking. For *,^2 you can use Karatsuba for more info see related QAs:

Also Division is possible using dividers like this (or any other approximation):

For more info you can look at source code of any bigint/bigdecimal lib out there.

Another way to deal with overflow/underflow is this:

Spektre
  • 49,595
  • 11
  • 110
  • 380