[Andrew Koenig] > By the way, has anyone considered the idea of making operations > on rationals faster by never storing any trailing zeroes in the > numerator or denominator? Instead, strip them and store the > (signed) difference between the number of zeroes you've stripped > from the numerator and the number you've stripped from the denominator. > > In other words, instead of storing (num, denom) and having the number > be the (exact) value of num/demon, store (num, denom, exp) and have the > number be the (exact) value of (2**exp)*num/denom. How many trailing zeroes do you expect to save this way? "On average", a random int has exactly n (>= 0) trailing zero bits with probability 1/2**(n+1). Then how expensive is it for operations to keep track of them appropriately (esp. + and -, where the split representation seems offhand (to me) unnatural to work with)? My FixedPoint.py does a variation of this for a form of unnormalized rational, except the "trailing zeroes" there are wrt base 10. But it wasn't to save time (heh) in that context, it was to create a faithful illusion of exact decimal arithmetic.
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4