From 6452c300366cf0e322227ad39991ec2fdfd6beed Mon Sep 17 00:00:00 2001 From: Denys Vlasenko Date: Tue, 22 Dec 2020 20:08:40 +0100 Subject: factor: detect squares If we have a square, the speedup can be extremely large (in best case example below, it's ~40000 times faster): $ time ./busybox_old factor 18446743988964486098 18446743988964486098: 2 3037000493 3037000493 real 0m4.246s $ time ./busybox factor 18446743988964486098 18446743988964486098: 2 3037000493 3037000493 real 0m0.000s function old new delta isqrt_odd - 57 +57 print_w - 36 +36 factorize 218 236 +18 print_h - 7 +7 factorize_numstr 65 72 +7 ------------------------------------------------------------------------------ (add/remove: 3/0 grow/shrink: 2/0 up/down: 125/0) Total: 125 bytes Signed-off-by: Denys Vlasenko --- testsuite/factor.tests | 23 +++++++++++++++++++++++ 1 file changed, 23 insertions(+) (limited to 'testsuite') diff --git a/testsuite/factor.tests b/testsuite/factor.tests index 2cf4a54ce..e404e29c1 100755 --- a/testsuite/factor.tests +++ b/testsuite/factor.tests @@ -45,4 +45,27 @@ testing "factor \$((2*3*5*7*11*13*17*19*23*29*31*37*41*43*47))" \ "614889782588491410: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47\n" \ "" "" +# Test that square-detection code is not buggy +testing "factor 2 * 3037000493 * 3037000493" \ + "factor 18446743988964486098" \ + "18446743988964486098: 2 3037000493 3037000493\n" \ + "" "" +testing "factor 3 * 2479700513 * 2479700513" \ + "factor 18446743902517389507" \ + "18446743902517389507: 3 2479700513 2479700513\n" \ + "" "" +# including square-of-square cases: +testing "factor 3 * 37831 * 37831 * 37831 * 37831" \ + "factor 6144867742934288163" \ + "6144867742934288163: 3 37831 37831 37831 37831\n" \ + "" "" +testing "factor 3 * 13^16" \ + "factor 1996249827549539523" \ + "1996249827549539523: 3 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13\n" \ + "" "" +testing "factor 13^16" \ + "factor 665416609183179841" \ + "665416609183179841: 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13 13\n" \ + "" "" + exit $FAILCOUNT -- cgit v1.2.3