commons-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Sebastien Riou (JIRA)" <j...@apache.org>
Subject [jira] [Updated] (MATH-841) gcd speed up
Date Mon, 13 Aug 2012 05:44:38 GMT

     [ https://issues.apache.org/jira/browse/MATH-841?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]

Sebastien Riou updated MATH-841:
--------------------------------

    Attachment: ArithmeticUtils.java
                patchGcdInt3.txt

Here is a new patch which comply with checkstyle. I kept the general "gcd" and "gcdPositive"
method separated to allow gcdPositive to be used directly within CM classes when we now for
sure that the numbers are positive. Please let me know if I missed something in your requests.
                
> gcd speed up
> ------------
>
>                 Key: MATH-841
>                 URL: https://issues.apache.org/jira/browse/MATH-841
>             Project: Commons Math
>          Issue Type: Improvement
>    Affects Versions: 3.0
>         Environment: ubuntu 32bits/intel-i5/java6
>            Reporter: Sebastien Riou
>            Priority: Trivial
>              Labels: patch, performance
>             Fix For: 3.1
>
>         Attachments: ArithmeticUtils.java, patchGcdInt3.txt
>
>   Original Estimate: 1h
>  Remaining Estimate: 1h
>
> The gcd(int,int) method of ArithmeticUtils seems 2 times slower than the naive approach
using modulo operator. The following test code runs in 11s with current version and in 6s
with the patch.
> public void testApache(){
>         Random rng=new Random(0);
>         long checksum=0;
>         long start=System.nanoTime();
>         checksum+=gcd(0,Integer.MAX_VALUE);
>         checksum+=gcd(Integer.MAX_VALUE,0);
>         checksum+=gcd(Integer.MAX_VALUE,rng.nextInt());
>         for(int i=0;i<10000;i++) checksum+=gcd(rng.nextInt(),Integer.MAX_VALUE);
>         checksum+=gcd(Integer.MAX_VALUE,Integer.MAX_VALUE);
>         checksum+=gcd(Integer.MIN_VALUE,1<<30);
>         checksum+=gcd(1<<30,1<<30);
>         checksum+=gcd(3 * (1<<20),9 * (1<<15));
>         for(int i=0;i<30000000;i++) checksum+=gcd(rng.nextInt(),rng.nextInt());
>         long end=System.nanoTime();
>         long tns=end-start;
>         long tms=(tns+500000)/1000000;
>         long ts=(tms+500)/1000;
>         System.out.println("exec time="+ts+"s, ("+tms+"ms), checksum="+checksum);
>         assertEquals(9023314441L,checksum);
>     }

--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira

        

Mime
View raw message