Re: efficiency bug in mpz_powm_ui?
Marc Glisse writes: I cannot see any recent snapshot at https://gmplib.org/download/snapshot/ , the most recent one appears to be from 17-Jan-2020. Ah, they are broken in the sense that they don't exist. :-) (It was a boched disabling of ftp snapshot downloads; the sync to the web server was disabled and the sync to the ftp server was left going. Script edit distance = 2. We want to disable inherently unsafe ftp downloads of unsigned stuff like the snapshots.) -- Torbjörn Please encrypt, key id 0xC8601622 ___ gmp-bugs mailing list gmp-bugs@gmplib.org https://gmplib.org/mailman/listinfo/gmp-bugs
Re: efficiency bug in mpz_powm_ui?
On Mon, 2 Mar 2020, Torbjörn Granlund wrote: paul zimmermann writes: PS: while trying the above change, I noticed the daily snapshots are broken since January 18... Would you mind telling us what is "broken"? I cannot see any recent snapshot at https://gmplib.org/download/snapshot/ , the most recent one appears to be from 17-Jan-2020. -- Marc Glisse ___ gmp-bugs mailing list gmp-bugs@gmplib.org https://gmplib.org/mailman/listinfo/gmp-bugs
Re: efficiency bug in mpz_powm_ui?
paul zimmermann writes: PS: while trying the above change, I noticed the daily snapshots are broken since January 18... Would you mind telling us what is "broken"? -- Torbjörn Please encrypt, key id 0xC8601622 ___ gmp-bugs mailing list gmp-bugs@gmplib.org https://gmplib.org/mailman/listinfo/gmp-bugs
Re: efficiency bug in mpz_powm_ui?
Dear Marco, > > it seems that mpz_powm_ui is highly inefficient when BASE^EXP has about > > the > > same size as MOD, in which case it could first compute BASE^EXP > > exactly, then > > perform only one reduction: > > You are right, mpz_powm_ui does not implement an algorithm that is > optimal for every possible use-case. But I'd not consider this a bug :-) > > > mpz_ui_pow_ui (x, 2, e); > > mpz_mod (r1, x, y); > > I'm not sure that mpz_ui_pow_ui (x, 2, e) is the more efficient way to > obtain a value x with only the bit e set to 1 :-) > But of course, in this context, the following _mod dominates > asymptotically. > > > mpz_set_ui (x, 2); > > mpz_powm_ui (r2, x, e, y); > > Thanks to a recent change, this function should be faster now, when base > is 2: > https://gmplib.org/repo/gmp/rev/63e53ddfd210 thank you, this solves the issue I reported. > Even if there is not jet any special code for the special case "BASE^EXP > has about the same size as MOD". indeed, the same issue can happen for other small values of BASE (not only 2). Best regards, Paul PS: while trying the above change, I noticed the daily snapshots are broken since January 18... ___ gmp-bugs mailing list gmp-bugs@gmplib.org https://gmplib.org/mailman/listinfo/gmp-bugs
Re: efficiency bug in mpz_powm_ui?
Ciao, Il 2020-02-29 11:54 paul zimmermann ha scritto: it seems that mpz_powm_ui is highly inefficient when BASE^EXP has about the same size as MOD, in which case it could first compute BASE^EXP exactly, then perform only one reduction: You are right, mpz_powm_ui does not implement an algorithm that is optimal for every possible use-case. But I'd not consider this a bug :-) mpz_ui_pow_ui (x, 2, e); mpz_mod (r1, x, y); I'm not sure that mpz_ui_pow_ui (x, 2, e) is the more efficient way to obtain a value x with only the bit e set to 1 :-) But of course, in this context, the following _mod dominates asymptotically. mpz_set_ui (x, 2); mpz_powm_ui (r2, x, e, y); Thanks to a recent change, this function should be faster now, when base is 2: https://gmplib.org/repo/gmp/rev/63e53ddfd210 Even if there is not jet any special code for the special case "BASE^EXP has about the same size as MOD". Ĝis, m ___ gmp-bugs mailing list gmp-bugs@gmplib.org https://gmplib.org/mailman/listinfo/gmp-bugs
