Here is my Magma script. Can anyone see anything wrong here?
bits:=2000000;
a:=RandomBits(bits);
b:=RandomBits(bits);
c:=RandomBits(bits);
a:=a*c;
b:=b*c;
time d:=Gcd(a,b);
Here for comparison is my GMP program:
#include <stdio.h>
#include <gmp.h>
#define bits 2000000
int main(void)
{
gmp_randstate_t state;
gmp_randinit_default(state);
mpz_t x;
mpz_t y;
mpz_t z;
mpz_init(x);
mpz_init(y);
mpz_init(z);
mpz_urandomb(x, state, bits);
mpz_urandomb(y, state, bits);
mpz_urandomb(z, state, bits);
mpz_mul(x, x, z);
mpz_mul(y, y, z);
printf("start\n");
mpz_gcd(z, x, y);
mpz_clear(x);
mpz_clear(y);
mpz_clear(z);
gmp_randclear(state);
}
Bill.
2008/11/5 Bill Hart <[EMAIL PROTECTED]>:
> Here are the times:
>
> Bit Size Magma eMPIRe+ eMPIRe-
> 2000000 1.500s 26.915s 35.497s
> 1000000 0.610s 5.794s 7.527s
> 500000 0.240s 1.440s 1.864s
> 250000 0.090s 0.312s 0.360s
> 100000 0.020s 0.040s 0.052s
> 50000 0.010s 0.012s 0.012s
>
> I begin to not believe the Magma times.
>
> SVN is not back up. Well it is locally for me, but I know nothing at
> all about apache, so I do not know how to start up the apache modules
> so everyone else can access it.
>
> Bill.
>
> 2008/11/5 Jason Martin <[EMAIL PROTECTED]>:
>>
>> Also, is SVN back up yet?
>>
>> Jason Worth Martin
>> Asst. Professor of Mathematics
>> http://www.math.jmu.edu/~martin
>>
>>
>>
>> On Wed, Nov 5, 2008 at 11:56 AM, Bill Hart <[EMAIL PROTECTED]> wrote:
>>>
>>> Ok I'll give it a go. Perhaps it'll turn up something stupid that I did.
>>>
>>> Bill.
>>>
>>> 2008/11/5 Jason Martin <[EMAIL PROTECTED]>:
>>>>
>>>> How about eMPIREe with Moller Patches versus eMPIREe without?
>>>>
>>>> Jason Worth Martin
>>>> Asst. Professor of Mathematics
>>>> http://www.math.jmu.edu/~martin
>>>>
>>>>
>>>>
>>>> On Wed, Nov 5, 2008 at 11:40 AM, Bill Hart <[EMAIL PROTECTED]> wrote:
>>>>>
>>>>> Yep, I timed Magma and eMPIRe with Moller's patches doing integer
>>>>> gcd's only on sage.math. Here is the table:
>>>>>
>>>>> Bit Size Magma eMPIRe
>>>>> 2000000 1.500s 26.915s
>>>>> 1000000 0.610s 5.794s
>>>>> 500000 0.240s 1.440s
>>>>> 250000 0.090s 0.312s
>>>>> 100000 0.020s 0.040s
>>>>> 50000 0.010s 0.012s
>>>>>
>>>>> Clearly the half-gcd is not working.
>>>>>
>>>>> Bill.
>>>>>
>>>>> 2008/11/5 Bill Hart <[EMAIL PROTECTED]>:
>>>>>> I plotted the poly gcd graph out to a higher bit size and now Magma is
>>>>>> clearly winning.
>>>>>>
>>>>>> The left most column is just integer GCD. Could it be that Magma
>>>>>> improves on Moller's gcd patches (I think I recall reading somewhere
>>>>>> that he originally wrote them for Magma), or did we do something wrong
>>>>>> when merging them?
>>>>>>
>>>>>> http://sage.math.washington.edu/home/wbhart/flint-trunk/graphing/gcd8.png
>>>>>>
>>>>>> Bill.
>>>>>>
>>>>>> 2008/11/1 Bill Hart <[EMAIL PROTECTED]>:
>>>>>>> Sorry, I simply mean you commit to the repo. I agree Mollers algorithm
>>>>>>> is clever and it should be pointed out that his paper on the topic is
>>>>>>> new work. He didn't just implement the half-BCD algorithm.
>>>>>>>
>>>>>>> Bill.
>>>>>>>
>>>>>>> On 01/11/2008, Jason Martin <[EMAIL PROTECTED]> wrote:
>>>>>>>>
>>>>>>>> Okay, I'll take a look at that when SVN is up again.
>>>>>>>>
>>>>>>>> Also, don't call them "Jason's Patches". That makes it sound like I
>>>>>>>> was clever... I wasn't. It's Moller's code, and his algorithm is very
>>>>>>>> very clever.
>>>>>>>>
>>>>>>>> --jason
>>>>>>>>
>>>>>>>> Jason Worth Martin
>>>>>>>> Asst. Professor of Mathematics
>>>>>>>> http://www.math.jmu.edu/~martin
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>> On Sat, Nov 1, 2008 at 9:55 AM, Bill Hart <[EMAIL PROTECTED]>
>>>>>>>> wrote:
>>>>>>>>>
>>>>>>>>> Jason, first bug report. When I build mpir with your patches (I have
>>>>>>>>> got the mpir repo working locally for me only - hopefully Michael will
>>>>>>>>> help me with the apache export so everyone else can get access again),
>>>>>>>>> I get warning messages in the compile on sage.math.
>>>>>>>>>
>>>>>>>>> gcd.c: In function 'mpz_rgcd':
>>>>>>>>> gcd.c:167: warning: implicit declaration of function 'mpn_rgcd'
>>>>>>>>> gcd.c: In function 'mpz_bgcd':
>>>>>>>>> gcd.c:171: warning: implicit declaration of function 'mpn_bgcd'
>>>>>>>>> gcd.c: In function 'mpz_sgcd':
>>>>>>>>> gcd.c:175: warning: implicit declaration of function 'mpn_sgcd'
>>>>>>>>> gcd.c: In function 'mpz_ngcd':
>>>>>>>>> gcd.c:179: warning: implicit declaration of function 'mpn_ngcd'
>>>>>>>>>
>>>>>>>>> It seems to build ok otherwise.
>>>>>>>>>
>>>>>>>>> Bill.
>>>>>>>>>
>>>>>>>>> 2008/11/1 Jason Martin <[EMAIL PROTECTED]>:
>>>>>>>>>>
>>>>>>>>>> On Fri, Oct 31, 2008 at 9:11 PM, mabshoff
>>>>>>>>>> <[EMAIL PROTECTED]> wrote:
>>>>>>>>>>> [snip]
>>>>>>>>>>> For me the highest priority item is the Moller's gcd code which has
>>>>>>>>>>> already been merged. What is the status of the code, i.e.
>>>>>>>>>>> performance,
>>>>>>>>>>> any known bugs, etc?
>>>>>>>>>>>
>>>>>>>>>>> Cheers,
>>>>>>>>>>>
>>>>>>>>>>> Michael
>>>>>>>>>>
>>>>>>>>>> Hi Michael,
>>>>>>>>>>
>>>>>>>>>> I haven't tested Moller's code beyond the standard make check test
>>>>>>>>>> suite (which passes all tests). I also haven't done any speed tests
>>>>>>>>>> other than the most rudimentary checks. So if anyone has some
>>>>>>>>>> suggestions for test cases, I'd be happy to try them out. Likewise,
>>>>>>>>>> if anyone has any bug reports for the gcd code, let me know and I'll
>>>>>>>>>> attempt to figure it out.
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> --jason
>>>>>>>>>>
>>>>>>>>>> >
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>> >
>>>>>>>>>
>>>>>>>>
>>>>>>>> >>>
>>>>>>>>
>>>>>>>
>>>>>>
>>>>>
>>>>> >
>>>>>
>>>>
>>>> >
>>>>
>>>
>>> >
>>>
>>
>> >>
>>
>
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"mpir-devel" group.
To post to this group, send email to mpir-devel@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups.google.com/group/mpir-devel?hl=en
-~----------~----~----~----~------~----~------~--~---
