This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Author tim.peters
Recipients mark.dickinson, rhettinger, tim.peters
Date 2019-08-15.19:19:27
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1565896767.81.0.870713229677.issue37863@roundup.psfhosted.org>
In-reply-to
Content
Well, details matter ;-)  Division in Python is expensive.  In the exponentiation algorithm each reduction (in general) requires a 122-by-61 bit division.  In egcd, after it gets going nothing exceeds 61 bits, and across iterations the inputs to the division step get smaller each time around.

So, e.g., when Raymond tried a Fraction with denominator 5813, "almost all" the egcd divisions involved inputs each with a single internal Python "digit".  But "almost all" the raise-to-the-(P-2) divisions involve a numerator with 5 internal digts and 3 in the denominator.  Big difference, even if the total number of divisions is about the same.
History
Date User Action Args
2019-08-15 19:19:27tim.peterssetrecipients: + tim.peters, rhettinger, mark.dickinson
2019-08-15 19:19:27tim.peterssetmessageid: <1565896767.81.0.870713229677.issue37863@roundup.psfhosted.org>
2019-08-15 19:19:27tim.peterslinkissue37863 messages
2019-08-15 19:19:27tim.peterscreate