the neverending rational vs. integer (they're really the same) saga

Jason Rennie jrennie@ai.mit.edu
Tue, 01 Aug 2000 14:03:59 -0400


I'm reading through some of your old e-mails.  Thought I'd make some 
comments...

sjmurdoch@linuxfan.com said:
> The only case I could forsee this would be if one could buy 1/3 of something
> or if prices were quoted as 1/3 of a dollar (or other currency unit).

So, one use for using rationals would be a form of error-checking.  If 
you type in 0.126 for 1/8, a rational representation could round 0.126
to 0.125 (1/8).

sjmurdoch@linuxfan.com said:
> My question is would it be *easier* to implement the modifications
> needed to Gnucash if another type and it's associated funcions were
> added to the API that could only represent integers (say stored as a
> 64bit integer)?

You could "derive" a "class" from gnc_numeric that assumes the 
denominator to be one.  This would simplify things the integer 
interface a bit.  I don't think having a completely separate 
gnc_integer type would simplify implementation though.

sjmurdoch@linuxfan.com said:
> However my gut instinct is that the implementation of things that
> *can* be represented as integers would be easier if they *were*
> represented of integers for several reasons, including: 

sjmurdoch@linuxfan.com said:
> It would not be necessary to keep track of giving functions the
> correct denominator. 

If I'm not mistaken, you don't have to pass a denominator to add,
subtract, etc.  Each gnc_numeric has a field indicating its denominator.
Is it not true that adding, subtracting or multiplying two gnc_numerics
with denominator=1 will always result in a gnc_numeric with denominator=1?

sjmurdoch@linuxfan.com said:
> Does not allow fractions to creep in where they are not allowed
> (multiplying two integrs will always give an integer, but ensuring
> that multiplying two gnc_numerics give an integer requires a little
> extra work that could be forgotten). 

Hmm... things are guaranteed to get a bit crazy when you multiply
different currencies.  This will happen whether you use Bill's rational
API or something else that represents most things as just integers.
Within a currency, Bill's API keeps things reasonably simple, although
one could make things even simpler.  When doing addition and subtraction
within a currency, you can safely ignore the denominator. Multiplication
and division are another story.

sjmurdoch@linuxfan.com said:
> Simplifies positive and negative values (does the numerator or
> denominator or bothedefine sign, and if both this complicates the
> comparison of values) 

It's easy enough to mandate in the API that (for example) only the
numerator can be negative.

On to your most recent e-mail...

sjmurdoch@linuxfan.com said:
> For example the task of comparing two integers is trivial O(1)
> complexity, but comparing two rationals is far from it and I think has
> O(sqr_root(n)) complexity, so if this is done several times the
> performance difference will be noticeable

How did you come up with these numbers?  What is `n'?  Comparing two 
rationals requires two stages: 1) converting to a common denominator, 
and 2) comparing the numerators as integers.  How does stage #1 take 
O(sqrt(n)) 
time?

sjmurdoch@linuxfan.com said:
> Calculations are done in SCU's when converting to major currencies[.]
> [T]his is more an issue of display (number of mills in a dollar has no
> significance in calculations), and is also a property of the commodity
> type, rather than the value. To put it in more concrete terms it is a
> proper[ty] of a column in the register window, rather than a cell.

Yup.  Having exactly one denominator per account would work just fine.  
Then additions and subtractions within that account could be done via 
integer operations.

sjmurdoch@linuxfan.com said:
> In general the integer representation would be better for quantities
> that have the property that between two distinct values there is a
> finite number of other values. Examples would be number of shares
> (pure integer), amount of currency (integer SCU's), bank balance
> (integer SCU's) etc...

So, I think the major difference between this concept and Bill's API is 
that all of the quantities in the same account are restricted to having 
the same denominator.  In other words, instead of having gnc_numeric 
have two integer elements, it might have one integer element (the 
numerator) and one pointer to another struct that contains the 
denominator for the account in which this value is stored.

sjmurdoch@linuxfan.com said:
> struct gnc_integer_commodity {
> 	char *fullname,
> 	char *mnemonic,
> 	char *namespace,
> 	char *currency_symbol,
> 	guint32 scus_per_major_unit
> 	};  

This is the same thing as Bill's API (with a different name for the SCU 
thingie).  Am I missing something here?

sjmurdoch@linuxfan.com said:
> The operations that will be used almost all the time are trivial
> (addition, subtraction, multiplication within a type, comparison) but
> share transactions and currency conversions deserve more explanation.

> guint64 transaction_total(guint64 quantity,
> 			guint64 price,
> 			guint32 scu_per_major_unit_in
> 			guint32 scu_per_major_unit_out
> 			char rounding) where transaction_total=round((quantity*price*scu_out
> )/scu_in) 

Hmm... this is exposing implementation details.  Might it not be better 
to combine "price" and "scu_per_major_unit_in" into a single 
gnc_numeric that knows about its SCUs?  Also, why don't we pass an 
output commodity instead of "scu_per_major_unit_out" (hence the user 
isn't forced to know the details of how a commodity is stored).

sjmurdoch@linuxfan.com said:
> uint64 currency_convert(guint64 in,
> 			guint32 scu_per_major_unit_in,
> 			guint64 rate,
> 			guint32 scu_per_major_unit_rate,
> 			guint32 scu_per_major_unit_out) 

Again, I'd rather see something like this:

gnc_numeric currency_convert (gnc_numeric in,
                              double rate,
                              gnc_commodity out,
                              char rounding);

I don't see it as too important to represent the rate exactly.  You'll 
have to do rounding no matter what.  Of course, it wouldn't hurt to 
represent it exactly:

gnc_numeric currency_convert (gnc_numeric in,
                              guint64 rate,
                              guint32 scu_per_major_unit_rate,
                              gnc_commodity out,
                              char rounding);

sjmurdoch@linuxfan.com said:
> The last two functions are quite similar to Bills, so you may ask the
> question what's the point of adding a new type to gnc_numeric.

I can't find a transaction total or a currency convert function in 
Bill's API.  Did I miss and updated API that he posted?

sjmurdoch@linuxfan.com said:
> One possible answer is efficiency; integer functions are far faster
> than rational ones and the majority of calculations are within type
> and only very rare cases currency_convert or transaction_total will be
> used.

Not really.  Rationals are essentially integers.  Rational calculations 
are speedy.  Anyway, this sort of thing may have been an issue when 
desktop machines barely topped the 1Mhz mark, but such things are 
hardly even worth thinking about nowadays.

sjmurdoch@linuxfan.com said:
> Most book keeping is done within a currency and this will be
> dramatically faster.

Nope.  Using the integer representation, you'll need one `if' statement 
to determine that you're dealing with two numbers of the same currency. 
 Bill can do the same to determine that he's dealing with two rationals 
with the same denominators.  With denominators being equal, Bill can 
ignore the denominator for the add/subtract and simply slap on the 
denominator when returning the final value.

sjmurdoch@linuxfan.com said:
> Also the storage required is about half the size, so decreasing memory
> usage, disk space and more importantly disk transfer time

You would get a win here---one denominator/SCU per account instead of 
one per number.

So, I think Bill's API is a great foundation.  One change that I think 
would make many happier would be to have the denominator of each number 
be represented by a (pointer to a) gnc_commodity.  This would make it 
easier to ensure one denominator per account without fully exposing the 
underlying rational representation.

Jason D Rennie                      www.ai.mit.edu/~jrennie/
MIT:  (617) 253-5339                      jrennie@ai.mit.edu
MITRE: (781) 271-7249                      jrennie@mitre.org