"Marco Bodrato" <bodr...@mail.dm.unipi.it> writes: Before you wake up, I send you another version. I added two more bits to the table entries, and started using one with some bit trickery (exploiting symmetries). It should be able to gain a bit of "speed", but in the unlikely case of operands of very different sizes only.
My code: 1.85 bits/iteration Your code: 2.60 bits/iteration It is worth remembering the table from my experiments with single-limb numbers: Algorithm Iterations Iter/Bit Bit/Iter Max iter plain binary : 834306161 0.697 1.435 59 binary+- : 726936855 0.607 1.647 58 binary+- alternating : 925657708 0.773 1.293 70 binary tab4 : 731982593 0.611 1.635 58 binary tab16 : 528194771 0.441 2.266 42 binary tab64 : 479879082 0.401 2.495 40 binary tab256 : 456126047 0.381 2.625 40 binary tab1024 : 434483855 0.363 2.755 36 binary tab4096 : 427124147 0.357 2.803 36 plain euclides : 690890073 0.577 1.733 63 euclides binary : 435552015 0.364 2.748 40 euclides 2-choice binary : 412937954 0.345 2.899 37 The now observed 2.60 bits/iteration is very close to the 2.625 bits/iteration from the table. (I looked briefly at your code, and don't understand it. I haven't had time for a proper look yet.) -- Torbjörn Please encrypt, key id 0xC8601622 _______________________________________________ gmp-devel mailing list gmp-devel@gmplib.org https://gmplib.org/mailman/listinfo/gmp-devel
