Implement the "unum" representation in D ?

[Ivan Kazmenko]

On Friday, 21 February 2014 at 20:27:18 UTC, Frustrated wrote:
> On Friday, 21 February 2014 at 09:04:40 UTC, Ivan Kazmenko 
> wrote:
>> Thus repeating decimal for a fraction p/q will take up to q-1 
>> bits when we store it as a repeating decimal, but 
>> log(p)+log(q) bits when stored as a rational number (numerator 
>> and denominator).
>
> No, you are comparing apples to oranges. The q is not the same 
> in both equations.

Huh?  I believe my q is actually the same q in both.

What I am saying is, more formally:

1. Representing p/q as a rational number asymptotically takes on 
the order of log(p)+log(q) bits.

2. Representing p/q as a repeating binary fraction asymptotically 
takes on the order of log(p)+q bits in the worst case, and this 
worst case is common.

Make that a decimal fraction instead of a binary fraction if you 
wish, the statement remains the same.

> The number of bits for p/q when p and q are stored separately is
> log[2](p) + log[2](q). But when p/q is stored as a repeating
> decimal(assuming it repeats), then it is a fixed constant
> dependent on the number of bits.

A rational represented as a fixed-base (binary, decimal, etc.) 
fraction always has a period.  Sometimes the period is 
degenerate, that is, consists of a single zero: 1/2 = 0.100000... 
= 0.1 as a binary fraction.  Sometimes there is a non-degenerate 
pre-period part before the period: 13/10 = 1.0100110011 = 
1.0(1001) as a binary fraction, the "1.0" part being the 
pre-period and the "(1001)" part the period.  The same goes for 
decimal fractions.

> So in some cases the rational expression is cheaper and in other
> cases the repeating decimal is cheaper.

Sure, it depends on the p and q, I was talking about the 
asymptotic case.  Say, for p and q uniformly distributed in 
[100..999], I believe the rational representation is much shorter 
on average.  We can measure that if the practical need arises... 
:)

In practice, one may argue that large prime denominators don't 
occur too often; well, for such applications, fine then.

> If n was large and fixed then I think statistically it would be
> best to use rational expressions rather than repeating decimals.

Yeah, that's similar to what I was trying to state.

> But rational expressions are not unique and that may cause some
> problems with representation... unless the cpu implemented some
> algorithms for reduction. 1/9 = 10/90 but 10/90 takes way more
> bits to represent than 1/9 even though they represent the same
> repeating decimal and the repeating decimals bits are fixed.

Given a rational, bringing it to lowest terms is as easy (yet 
costly) as calculating the GCD.

> In any case, if the fpu had a history of calculations it could
> potentially store the calculations in an expression tree and
> attempt to reduce them. e.g., p/q*(q/p) = 1. A history could 
> also be useful for constants in that multiplying several 
> constants
> together could produce a new constant which would not introduce
> any new accumulation errors.

As far as I know, most compilers do that for constants known at 
compile time.  As for the run-time usage of constants, note that 
the pool of constants will still have to be stored somewhere, and 
addressed somehow, and this may cancel out the performance gains.

Ivan Kazmenko.