[
https://issues.apache.org/jira/browse/NUMBERS-79?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16852413#comment-16852413
]
Heinrich Bohne edited comment on NUMBERS-79 at 5/30/19 10:33 PM:
-----------------------------------------------------------------
I found this ticket by accident, and it made me think. And the more I have
thought about it, the more convinced I am that the calculation where the
original code claims to require 65 bits of precision can, in fact, _always_ be
performed using only {{long}} values without causing overflow. First, to
recollect the problem at hand:
The objective is to calculate ^m^⁄~a~ + ^n^⁄~b~, where m is coprime to a and n
is coprime to b. Now, let d be the greatest common divisor of a and b, then the
calculation becomes
^m^⁄~p⋅d~ + ^n^⁄~q⋅d~
, where p and q are coprime, and m is coprime to p and d, and n is coprime to q
and d. Continuing this, we get:
^m^⁄~p⋅d~ + ^n^⁄~q⋅d~
= ^m⋅q^⁄~p⋅q⋅d~ + ^n⋅p^⁄~p⋅q⋅d~
= ^m⋅q + n⋅p^⁄~p⋅q⋅d~
The variables m, n, p and q can all be represented as an {{int}}, therefore,
the terms m⋅q and n⋅p can each be represented as a {{long}}. The question is,
can m⋅q + n⋅p be represented as a {{long}}? To examine this, let's consider the
worst case scenario, where every one of these 4 variables has the largest
possible absolute value an {{int}} can have, which is 2^31^. This is only
possible if the {{int}} value is negative, i.e. -2^31^. So then, our numerator
term becomes:
m⋅q + n⋅p
= (-2^31^) ⋅ (-2^31^) + (-2^31^) ⋅ (-2^31^)
= 2^63^
, which exceeds the largest possible {{long}} value only by one. However, this
scenario will never arise, because m and p are coprime, just like n and q are
coprime and q and p are coprime. So these 4 variables cannot all be -2^31^,
which means that the absolute value of the term m⋅q + n⋅p _must_ be smaller
than 2^63^ and therefore representable as a {{long}}.
Perhaps the source the code comments refer to is talking about unsigned
integers, in which case 64 bits would indeed not be enough, as far as I can
tell.
However, the current version in the fraction-dev branch, which, I assume,
contains the fix to this ticket's issue, restricts even the intermediate values
in the above calculation to {{int}} instead of {{long}} type, which would be
what this ticket suggests. This creates the problem of throwing an exception
even if the final value can be represented as an {{int}}, because, while m⋅q +
n⋅p is definitely coprime to p and q, it could potentially share a factor with
d, so even if m⋅q + n⋅p cannot be represent as an {{int}}, the final numerator
could. For example:
^362,564,597^⁄~10~ + ^274,164,323^⁄~6~ = ^1,229,257,703^⁄~15~
All numerators and denominators of these fractions can be expressed as an
{{int}}, but the current code in fraction-dev fails to calculate this sum,
because it restricts even intermediate values to type {{int}}, and not just the
final values. If it were to store and perform calculations on intermediate
values as {{long}} variables, then it would work.
Since the data type {{long}} will always be sufficient for intermediate values,
thus eliminating the need for {{BigInteger}}, I don't see a reason to use
{{int}} instead of {{long}} values if this could cause the method to fail when
it would otherwise calculate the correct result.
was (Author: schamschi):
I found this ticket by accident, and it made me think. And the more I have
thought about it, the more convinced I am that the calculation where the
original code claims to require 65 bits of precision can, in fact, _always_ be
performed using only {{long}} values without causing overflow. First, to
recollect the problem at hand:
The objective is to calculate ^m^⁄~a~ + ^n^⁄~b~, where m is coprime to a and n
is coprime to b. Now, let d be the greatest common divisor of a and b, then the
calculation becomes
^m^⁄~p⋅d~ + ^n^⁄~q⋅d~
, where p and q are coprime, and m is coprime to p and d, and n is coprime to q
and d. Continuing this, we get:
^m^⁄~p⋅d~ + ^n^⁄~q⋅d~
= ^m⋅q^⁄~p⋅q⋅d~ + ^n⋅p^⁄~p⋅q⋅d~
= ^m⋅q + n⋅p^⁄~p⋅q⋅d~
The variables m, n, p and q can all be represented as an {{int}}, therefore,
the terms m⋅q and n⋅p can each be represented as a {{long}}. The question is,
can m⋅q + n⋅p be represented as a {{long}}? To examine this, let's consider the
worst case scenario, where every one of these 4 variables has the largest
possible absolute value an {{int}} can have, which is 2^31^. This is only
possible if the {{int}} value is negative, i.e. -2^31^. So then, our numerator
term becomes:
m⋅q + n⋅p
= (-2^31^) ⋅ (-2^31^) + (-2^31^) ⋅ (-2^31^)
= 2^63^
, which exceeds the largest possible {{long}} value only by one. However, this
scenario will never arise, because m and p are coprime, just like n and q are
coprime and q and p are coprime. So these 4 variables cannot all be -2^31^,
which means that the absolute value of the term m⋅q + n⋅p _must_ be smaller
than 2^63^ and therefore representable as a {{long}}.
Perhaps the source the code comments refer to is talking about unsigned
integers, in which case 64 bits would indeed not be enough, as far as I can
tell.
However, the current version in the fraction-dev branch, which, I assume,
contains the fix to this ticket's issue, restricts even the intermediate values
in the above calculation to {{int}}s instead of {{longs}}, which would be what
this ticket suggests. This creates the problem of throwing an exception even if
the final value can be represented as an {{int}}, because, while m⋅q + n⋅p is
definitely coprime to p and q, it could potentially share a factor with d, so
even if m⋅q + n⋅p cannot be represent as an {{int}}, the final numerator could.
For example:
^362,564,597^⁄~10~ + ^274,164,323^⁄~6~ = ^1,229,257,703^⁄~15~
All numerators and denominators of these fractions can be expressed as an
{{int}}, but the current code in fraction-dev fails to calculate this sum,
because it restricts even intermediate values to {{int}}s, and not just the
final values. If it were to store and perform calculations on intermediate
values as {{long}}s, then it would work.
Since the data type {{long}} will always be sufficient for intermediate values,
thus eliminating the need for {{BigInteger}}s, I don't see a reason to use
{{int}}s instead of {{long}}s if this could cause the method to fail when it
would otherwise calculate the correct result.
> Convert fraction addition from BigInteger-based to long-based
> -------------------------------------------------------------
>
> Key: NUMBERS-79
> URL: https://issues.apache.org/jira/browse/NUMBERS-79
> Project: Commons Numbers
> Issue Type: Improvement
> Reporter: Eric Barnhill
> Assignee: Eric Barnhill
> Priority: Minor
>
> Current Fraction class uses BigInteger due to the fact that in extreme cases
> adding and subtraction of fractions can require 65 bits of precision. However
> this is very costly in terms of performance for all but the most extreme
> cases. This ticket proposes using long-based arithmetic for Fraction addition
> and subtraction, and recommending BigFraction if the operation may run very
> large.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
