Re: [numbers] Fraction() and Knuth 4.5.1 -- overflow, BigInteger, long, and rounding

[Eric Barnhill]

Addendum to the above. In an exercise in the Knuth book Knuth does indeed
state that "If the inputs are n-bit binary numbers, 2N+1 bits may be
necessary to represent t." where t is a derived quantity that would take
some time to explain.

So that means in extreme cases, the needed precision to represent a
fraction operation with 32 bits ints is 65 bits, one more than a long has.

The present code solves this by using BigInteger briefly in the code, which
strikes me as an awfully big performance hit for what must surely be very
occasional and very  extreme cases.

I think the most sensible strategy would be to restrict the precision of
Fraction to longs, with user guidance to use BigFraction if there is
concern of overflow.

Eric







On Thu, Nov 8, 2018 at 11:11 AM Gary Gregory  wrote:

> I'm all for the Javadoc made to reflect the reality of the code. It is fine
> to have an additional section that points out Knuth and how we may want to
> change things as a hint or request to contributors.
>
> Gary
>
> On Wed, Nov 7, 2018 at 10:52 AM Eric Barnhill 
> wrote:
>
> > I read Kunth's "Art of Computer Programming 4.5.1" that is referenced
> many
> > times in the doc as the guidance for the commons-math/commons-numbers
> > Fraction class. It is an interesting read. Also, for all the times it is
> > cited in the doc, it is interesting that Fraction doesn't really use it
> as
> > implemented. Here is one example.
> >
> > Knuth is concerned about overflow in multiplication and division, because
> > numerator of f1 is multiplied by denominator of f2 and so forth, so he
> > suggests a technique called "mediant rounding" that allows for
> intermediate
> > quantities in fraction multiplication to be rounded.
> >
> > It is a clever technique and probably works well, however the current
> > Fraction class cites this chapter, then implements multiplication with
> > BigInteger instead, ignoring this suggestion.
> >
> > First of all, the doc should be clear that the code is NOT following
> 4.5.1,
> > while it gives the opposite impression. And that's ok but the use of
> > BigInteger creates additional inconsistency: Multiply and divide are
> > accomplished using ArithmeticUtils.addAndCheck and
> > ArithmeticUtils.mulAndCheck . These convert the relevant ints to longs,
> > then perform the operation, then if the resulting long is greater than
> the
> > range of an int, throw an OverflowException. So some parts of Fraction
> > check for overflow using longs and others use BigInteger.
> >
> > It seems to me that BigInteger is overkill here for the vast majority of
> > practical uses of Fraction in a way that could be damaging for
> performance.
> > And furthermore, we already have a BigFraction class to handle cases that
> > require BigInteger.
> >
> > So, I propose rewriting the doc to say the opposite of what it currently
> > says when appropriate, and get usages of BigInteger out of Fraction, use
> > them only in BigFraction, and use the long-based ArithmeticUtils methods
> to
> > check for overflow and underflow in fraction addition and subtraction.
> >
> > Eric
> >
>

[GitHub] commons-collections issue #57: COLLECTIONS-701 SetUniqueList.add() crashes d...

[drajakumar]

Github user drajakumar commented on the issue:

https://github.com/apache/commons-collections/pull/57
  
sure @garydgregory  i am analyzing for a fix as per the expectation, will 
update you.


---

-
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org

[GitHub] commons-collections issue #57: COLLECTIONS-701 SetUniqueList.add() crashes d...

[garydgregory]

Github user garydgregory commented on the issue:

https://github.com/apache/commons-collections/pull/57
  
You did not have to close the PR, I was hoping you would provide a more 
complete solution ;-)


---

-
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org

[GitHub] commons-collections pull request #57: COLLECTIONS-701 SetUniqueList.add() cr...

[drajakumar]

Github user drajakumar closed the pull request at:

https://github.com/apache/commons-collections/pull/57


---

-
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org

[GitHub] commons-collections issue #57: COLLECTIONS-701 SetUniqueList.add() crashes d...

[drajakumar]

Github user drajakumar commented on the issue:

https://github.com/apache/commons-collections/pull/57
  
closing the pr as the fix is not as expected


---

-
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org

[GitHub] commons-collections pull request #57: COLLECTIONS-701 SetUniqueList.add() cr...

[drajakumar]

Github user drajakumar closed the pull request at:

https://github.com/apache/commons-collections/pull/57


---

-
To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
For additional commands, e-mail: dev-h...@commons.apache.org

JDK 12 , JDK 8u202 & Project Panama Early-Access builds available

[Rory O'Donnell]

Hi Benedikt,

*JDK 12 Early Access build 19 is available at : - jdk.java.net/12/*

 * These early-access, open-source builds are provided under the GNU
   General Public License, version 2, with the Classpath Exception
   .

 * Release Notes updates since last email
 o Build 18 – JDK-8211883: Disable anon and NULL cipher suites
 + Crypto Roadmap
    Updated
 o Build 17 – JDK-8211806: TLS 1.3 handshake server name indication
   is missing on a session resume
 o Build 16 – JDK-8211866: TLS 1.3 CertificateRequest message
   sometimes offers disallowed signature algorithms
 o Build 17 – JDK-8195793 : Remove GTE CyberTrust Global Root
 o Build 16 - JDK-8191053 : Provide a mechanism to make system's
   security manager immutable

 * JEPs proposed for JDK 12 so far:
 o JEP 230 - Microbenchmark Suite 
 * JEPs targeted to JDK 12, so far
 o 325: Switch Expressions (Preview) 
 o 326: Raw String Literals (Preview)
   
 o 340: One AArch64 Port, Not Two 
 o 341: Default CDS Archives 

*JDK 8u202 Early Access build 03 is available at : - 
**http://jdk.java.net/8/*


 * JDK 8u202 timeline is available [1]
 o GA is scheduled for January 2019

*Project Panama Early-Access build 0 ***is available at : - 
http://jdk.java.net/panama/

**

 * Early access builds from Project Panama
   
 * Early-access builds are provided under the GNU General Public
   License, version 2, with the Classpath Exception
   .
 * Feedback - Please send feedback via e-mail to
   panama-...@openjdk.java.net .
 * To send e-mail to this address you must first subscribe to the
   mailing list
   .

*Crypto Roadmap Updated [2]
*


Rgds,Rory

[1] http://openjdk.java.net/projects/jdk8u/releases/8u202.html
[2] https://java.com/en/jre-jdk-cryptoroadmap.html

--
Rgds,Rory O'Donnell
Quality Engineering Manager
Oracle EMEA , Dublin, Ireland