From unknown Wed Jun 18 00:09:08 2025 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-Mailer: MIME-tools 5.509 (Entity 5.509) Content-Type: text/plain; charset=utf-8 From: bug#59636 <59636@debbugs.gnu.org> To: bug#59636 <59636@debbugs.gnu.org> Subject: Status: prime [ factor ] utility very slow in factoring the square of a prime Reply-To: bug#59636 <59636@debbugs.gnu.org> Date: Wed, 18 Jun 2025 07:09:08 +0000 retitle 59636 prime [ factor ] utility very slow in factoring the square of= a prime reassign 59636 coreutils submitter 59636 "Jason C. Kwan" severity 59636 normal thanks From debbugs-submit-bounces@debbugs.gnu.org Sun Nov 27 12:00:59 2022 Received: (at submit) by debbugs.gnu.org; 27 Nov 2022 17:00:59 +0000 Received: from localhost ([127.0.0.1]:43100 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ozL1W-0006k1-4d for submit@debbugs.gnu.org; Sun, 27 Nov 2022 12:00:59 -0500 Received: from lists.gnu.org ([209.51.188.17]:59832) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ozIy8-0005TJ-29 for submit@debbugs.gnu.org; Sun, 27 Nov 2022 09:49:20 -0500 Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1ozIy7-0005KH-SH for bug-coreutils@gnu.org; Sun, 27 Nov 2022 09:49:19 -0500 Received: from sonic305-21.consmr.mail.ne1.yahoo.com ([66.163.185.147]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1ozIy4-0007dW-NK for bug-coreutils@gnu.org; Sun, 27 Nov 2022 09:49:19 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yahoo.com; s=s2048; t=1669560550; bh=LgouSuNJ7gGbP3IX8KToNEjbBuD4mfdnaDX1rUpgo+I=; h=Date:From:To:Subject:References:From:Subject:Reply-To; b=pDaXu5USiTa7uoj4zk8c8wiAzdI/+kjjB9YV+OECL/BCLCWlzO7Whffqro60VmrORFkUKFtYZEH52mFMlKxJ5dAhXCKmKc9qHW4/pMKxH+OFrNuu3eWIcBFLKzVjcCJOezzt+Rp5CoX72kEaXIlhx8yew6O9nyy6Bn9Afh4BOj3/5mWDkVI6oJQuzTAzV1M5J78Gq5SwHDelYk4mCCVZOKWAeKd9Wx+wz9hvRqZew7PoRA5V6UMIxQ+C8nMCRztKoeJvTq4M3jr4i1HE/CEjUsvdPBr8AA4Fk6x1jI5h4w/CTCJTtr5j26Ml/gD/zAFNTukpzKXX68vqyiBMHqX2ig== X-SONIC-DKIM-SIGN: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yahoo.com; s=s2048; t=1669560550; bh=zvoPpTriFYFF3oG41Gt6McWr7qjz8jZr6SWnMBje276=; h=X-Sonic-MF:Date:From:To:Subject:From:Subject; b=gF08o5WWs+g0zs0xcIXEl1B5dTy5f3rvyr4D29TL5Z9xwGHGFnmL02+3qY2AGjbaR6YLOAr28fH8re4i6DwfatD25WZw3FUiK3BL43XwDJ0a5+gNMkGTYELChZdtAwgNSfNIl6DXCfEQE/iHXTTzinDAePR9aDnWDI/Yt3D85bvafbJ5q5L4Hh7O2bolRs0b1BjEABDii722QZ1vx3hpC3xS3I3m6k+1IqBGh7uK01peIjAoHL3uaWy+fpTfsDm8ymvZCT/dPbZfUL9ampFc7jKUxn/3b2/3iN4SL+w4TAZpG/MpEYit1pxj97JA2R8TJnw6H/CUNAbRIcztAWMgfw== X-YMail-OSG: RVZ10AIVM1kt_0bK_Yij8XDYaG8io47l1fvqP_SzGJlYRGNVFJcG0BIUJk_nuQe ZnvE0lWm9oVuAn_PRT5fS6vRQyZlDRXYElCZ3qogk3FlPWDGaRm39fa9agy9VIjd7J1RU1KOJFu6 DFw9CI7yBwfglKrscEoztB1PRxf.Xf28YWn2vSsrwKpgzR5N7WVPPUqmU78h4OpkEG76wR6.p.1C PKrcaJ2ObOO0Z_Iryv777V2N_hVSLrLRCiteGN3r1BfD5mY5swbB5O238v9sKw.r0wHTWc3IgyKI rGOHk4rDPIKdALH.5juql8QDNVjH.eiU9xGdZesqu0JJhOE.tKgXzwqRieMapkyAjprXNpdFgnEj jSDh9X9dtv3KTFgIYJ0qfn4VjC_WXi5xbefz6UsAwfAG7CP_48SjI1mYYM_lXL8V9HsQLH0c8pDj D3Dfv97tUCDJS8eWi1ZGDly78vWfXwQ2CuK.kPxlBVGq3UQXgaLAd_8UBmo2tR.kev7I2qYPQJ8w 8tOvl6SbjRzXseK71aM9HpP4blOcUf5AC0fJy9SsPvpPhHIzji23Z9G98TKzmRJoKoCrQ2jcVj1C Ing8I_lur_v0Kquc3_DuFk1PryUp4Pk.DsvGgIDyLz4BnAz8HKLmLnnGsai2eKOCUzp67ou_GD1L 1XIQeUPcakQ8CFMSM9DhqJGluU8vuxSnLFljKNxEd7WZnKd7afAKTXNACbC8f0vC4wuizHw4IyOW 7KUfpx.Be3I7aToEQ1KkwQi3HIaT6Rer8.6B_C2KuQMiCeDYASbTQAsdqNfQKNpamTvS9bJ2dNKC 2rlHZip2_LV7.iQavDD1CpauQ1Ruv_uDS7SA3JR8qhk5SdcSdaUlxzjhd7czWhiUPpDsVKDVOzgQ F4OvjpC4C5Brd8OgJTvtLq3TPZRTjIT73WEJvb6ytYq9xcbfgr5EGx8RAGAIDySIlZWeUF3EFCOb zYMxc1qCxw1Tn09QwAViF0olRwhu15JOCJz0nWm.Dj1b7VHQs1yy1Wrg1qAfiRTpnJ8n9.JJW6Nn msoI6Q5p_fx0qwnoyO5F.oIKUhGLcO1KPg04Mj_Mk87t47YTvVq5pLOIfhjZtfszlQJ1pX6leDRX vG.dZxrYqFgCeUMdIvm7vYCUGYXABzJ.OB388bkRMGvG38Q1xJoOuFOnZNqay1R1V49LfbBs0bt5 uKdlCK437_tNwJMcdpJuru3deSqllj2SFMbUpnsXuaGyHiu6P0gxfOCktzF.I9I4cjBU82QgPLtg 5Xj0AjfLYwOHvOGSBBbh.pKhbfmqCH6BH6lN7YVU9vAFT5cdUfQTuXOf_q5EBzHrBEw84q6D1Wmz pzxmia7Ozbq4gIsBp0ZFPOjD7lHLiL_a20MS1uIIk8BSszHZ38N743E_KwyYdWem8OBJ379sbhLX VN3cOFtxVrnPqr81yeQfQAhwNlJKsudSLTmeLj9chSA7uEXFrdAFhXrqjyNjLdtvEQKGP1JFcID. IP_8tGCwSK7y5i02m3BNUqf1CYkRcVsGtthspktIMFHVrGs7cfXAvJfQRT27g9ZptrtwLuU6rHvO FA.q5q4WjhW1aDvVxoXEIBjivu1B5rTH0hDq3jJvmvFmIdiRhcVulfxzk4mfCYZeUZj.qUO4n.oD j2OMdDjxGvTBoFvmaARoUAOXstWD8yBl3Pup7YJF34MtixsS1pIfqacEZ0GsWA95zBPbcfWP7smT uxtyDPgLT2qR2KEiKkGjCrE26AuM79UT.6QbGCx8bBGlChZvApgDvD0wu7yUePqTb8uTYggY9FNk kljuQOm0ADqD32HSbshUWCHv4x_E04Kq684bkShKzxkgpWpaKnZzL5LZRDj6B6V9AEk0p3nbUH55 wXHh4lUtmWUxRDQ.qYc7Jewq5bvO7POxr.8D2be71aa6dAUxl317ie1lvFMlubeC1siOz4cJCDKi SlF.Vg8LpZq9M2mUmJMvtTNUXwcP6q1rhBDRGOBz.i0nAblG78geHHysEBaFRK7.zv4oVy8o5NPN FDoS2cH1k6PbKbhpsJtgarZo4WAQp9GLvFlqfmda2SHjViesSHArrAiWz6CNLJropW8vS2RuYFN1 eLGg95WRbfe81i.PjTegY1gfG2oBKAPWUTxorBpKBlOOYNo5SEvxvxb3vTYsK0Fh2Yf9KI1B7X0e 5w5RsnO0iMBE1yjEI5VQSpy4q1pgcKvuAy3cmrd8oKwNVVajgDGNi0nWHnMRJOVb1U365FrpIAlT tVLGy95rDzT6hrJLVAurpdFkj7ydiH5Q- X-Sonic-MF: Received: from sonic.gate.mail.ne1.yahoo.com by sonic305.consmr.mail.ne1.yahoo.com with HTTP; Sun, 27 Nov 2022 14:49:10 +0000 Date: Sun, 27 Nov 2022 14:48:16 +0000 (UTC) From: "Jason C. Kwan" To: bug-coreutils@gnu.org Message-ID: <1074878990.5154226.1669560496803@mail.yahoo.com> Subject: prime [ factor ] utility very slow in factoring the square of a prime MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_Part_5154225_245599714.1669560496798" References: <1074878990.5154226.1669560496803.ref@mail.yahoo.com> X-Mailer: WebService/1.1.20863 YMailNorrin Content-Length: 20780 Received-SPF: pass client-ip=66.163.185.147; envelope-from=jasonckwan@yahoo.com; helo=sonic305-21.consmr.mail.ne1.yahoo.com X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-Spam-Score: -0.6 (/) X-Debbugs-Envelope-To: submit X-Mailman-Approved-At: Sun, 27 Nov 2022 12:00:57 -0500 X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -1.6 (-) ------=_Part_5154225_245599714.1669560496798 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable The test case is=C2=A0 =C2=A0 =C2=A0 =C2=A0 49,456,902,806,087,647,575,555,655,201 a prime that is approx. 95.3-bits in size,=C2=A0plus the direct squaring of= it, ascalculated by gnu-bc=C2=A0 =C2=A0 =C2=A0 (see full text below for host system info,=C2=A0=C2=A0 =C2=A0= =C2=A0versioning details, and command line=C2=A0=C2=A0 =C2=A0 =C2=A0statem= ents=C2=A0used to perform this test.=C2=A0 =C2=A0 =C2=A0 =C2=A0 xargs used is macOS 12.6 built-in one instead of GNU o= ne) The base prime has a hex representation is=C2=A0 =C2=A0 =C2=A0 =C2=A0 0x 9FCD CA89 5696 76C0 0B03 4621 The issue being that while it took the [ factor ] utility just=C2=A0shy of = 4.8ms to complete its primality checks, and confirmed the=C2=A0first input = is indeed prime,=C2=A0 attempting to factor the direct squaring of the same prime resultedin the t= ask being timed=C2=A0out after 1200 seconds, or 20 minutes. Perhaps there is an opportunity to optimize it by=C2=A0 =20 - performing=C2=A0a quick square/square-root=C2=A0check for large inputs= =20 =C2=A0 =C2=A0 =C2=A0(e.g. >=3D 2^127, per "info factor")=C2=A0 before routing it to what=C2=A0"info factor"=C2=A0refers=C2=A0to as=C2=A0"t= he slower algorithm" ? Maybe also add one more cube/cube-root quick check if the=C2=A0relative=C2= =A0cost to system resources isn't particularly material ? RegardsJason % uname -mrsv=C2=A0 =C2=A0 =C2=A0 =C2=A0 Darwin 21.6.0 Darwin Kernel Version 21.6.0:=C2=A0=C2= =A0 =C2=A0 =C2=A0 Mon Aug 22 20:19:52 PDT 2022;=C2=A0 =C2=A0 =C2=A0 =C2=A0 root:xnu- =C2=A08020.140.49~2/RELEASE_ARM64_T6000 arm6= 4 % gdate=C2=A0 gfactor --version=C2=A0 =C2=A0 =C2=A0 =C2=A0bc --version =C2=A0 =C2=A0 =C2=A0 Sun Nov 27 03:34:47 EST 2022 --------------------------------------------- factor (GNU coreutils) 9.1Copyright (C) 2022 Free Software Foundation, Inc.= License GPLv3+: GNU GPL version 3 or later .This is free software: you are free to change and redistribute it.There= is NO WARRANTY, to the extent permitted by law. --------------------------------------------- Written by Paul Rubin, Torbj=C3=B6rn Granlund, and Niels M=C3=B6ller.bc 1.0= 6Copyright 1991-1994, 1997, 1998, 2000 Free Software Foundation, Inc. --------------------------------------------- =C2=A0 echo ' x =3D 49456902806087647575555655201 ; x^1 ; x^2 ; ' |=C2=A0= =C2=A0 bc =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 |=C2=A0=C2=A0 xargs -t= -n 1 -P 2 timeout --foreground 1200 gfactor =C2=A0 =C2=A0 |=C2=A0 =C2=A0 awk '=C2=A0 function ep16(__,_,___) {=C2=A0=C2=A0 =C2=A0 =C2=A0 retu= rn substr("",=C2=A0=C2=A0 =C2=A0 =C2=A0 =C2=A0(___ =3D RS) * (RS =3D "\n") = * \=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0( (__ =3D " gdate +\"%s%6N\" ")= | getline _),=C2=A0=C2=A0 =C2=A0 =C2=A0 =C2=A0close( __) ^ (RS =3D ___))_= =C2=A0=C2=A0 } =C2=A0 function timer(_,__) {=C2=A0=C2=A0 =C2=A0 =C2=A0 return \=C2=A0 =C2= =A0 =C2=A0 +_ < (__=3D ep16())^(_<_) \=C2=A0 =C2=A0 =C2=A0 ? =C2=A0 __\=C2= =A0 =C2=A0 =C2=A0 : (__-_) /\=C2=A0 =C2=A0 =C2=A0 =C2=A0 ( ( (_+=3D_^=3D_<_= )+_*_*_)^(_ +_+ =C2=A0_)*\=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 ( _++^!= ++_ + =C2=A0 =C2=A0_^-(_ +_+--_) ) )=C2=A0 }=C2=A0 BEGIN { =C2=A0__=C2=A0= =3D timer(_ =3D _<_)=C2=A0 =C2=A0 =C2=A0 =C2=A0 OFMT =3D "%.25g"=C2=A0=C2= =A0 =C2=A0 CONVFMT =3D "%.250g"=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 _^=3D_=C2= =A0 } =C2=A0($++NF =3D sprintf("%.13f", timer(__)))^!_ +\=C2=A0 =C2=A0 =C2= =A0($++NF =3D =C2=A0 =C2=A0 =C2=A0 =C2=A0log( $_ ) / log(_+_))^!_'=C2=A0 --------------------------------------------- timeout --foreground 1200 gfactor 49456902806087647575555655201timeout --fo= reground 1200 gfactor 24459852351708002288868828435365115722991163278523983= 50401 49456902806087647575555655201: 49456902806087647575555655201 0.004790999999= 9 95.320158551927676171544590033590793609619140625 ------=_Part_5154225_245599714.1669560496798 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
The test case is 

    =   49,456,902,806,087,647,575,555,655,201

a prime that is approx. 95.3-bits= in size, 
plus the direct squaring of it, as
calculated by gnu-bc 

&nb= sp;   (see full text below for host system info, 
     versioning details, = and command line 
&n= bsp;    statements used to perfor= m this test. 


The base prime has a hex representation is&nbs= p;

<= div dir=3D"ltr" data-setdir=3D"false">      0x 9FCD CA89 5696 76C= 0 0B03 4621

The issue being that while it took the [ factor ] utility just&= nbsp;
shy of 4.8ms to com= plete its primality checks, and confirmed the 
first input is indeed prime, 

attempting to factor the direct squaring of the same prime= resulted
in the task bei= ng timed out after 1200 seconds, or 20 minu= tes.

<= font face=3D"courier new, courier, monaco, monospace, sans-serif">Perhap= s there is an opportunity to optimize it by 
  • performing a quick square/squa= re-root check for large inputs
    • =
  &n= bsp;  (e.g. >=3D 2^127, per "info factor") 

before routing it to what "info factor" refers to as "the slower algorithm" ?

Maybe also add one more= cube/cube-root quick check if the 
relative cost to sys= tem resources isn't particularly material ?

<= div><= br>
Regards
Jason

=

% uname -mrsv 

      Darwin 21.6= .0 Darwin Kernel Version 21.6.0:
 
  &nb= sp;   Mon Aug 22 20:19:52 PDT 2022; 

<= b>      root:xnu-  8020.140.49~2/RELEASE_ARM64_T6000 ar= m64

% gdate
  gfactor --version
       bc --v= ersion


<= div>&= nbsp;     Sun Nov 27 03:34:47 EST 2022

---------------------------------------------

=
= factor (GNU coreutils) 9.1
Copyright (C) 2022 Free Software= Foundation, Inc.
License GPLv3+: GNU GPL version 3 or late= r <https://gnu.org/licenses/gpl.html>.
This is free s= oftware: you are free to change and redistribute it.
<= font face=3D"courier new, courier, monaco, monospace, sans-serif">There = is NO WARRANTY, to the extent permitted by law.

---------------------------------------------

Written by Paul Rubin, Torbj=C3=B6rn Granlund,= and Niels M=C3=B6ller.
bc 1.06
Copyright 1= 991-1994, 1997, 1998, 2000 Free Software Foundation, Inc.
<= div><= br>
---------------------------------------------

<= div>&= nbsp; echo ' x =3D 49456902806087647575555655201 ; x^1 ; x^2 ; ' | 
  bc               &n= bsp;                     =                   | <= /font>
  xargs -t -n 1 -P 2 timeout --foreground 1200 gfactor &nb= sp;   | 

  awk '
  function ep16(__,_,___) { 
  &nb= sp;   return substr("", 
      &nb= sp;(___ =3D RS) * (RS =3D "\n") * \
      &n= bsp;    ( (__ =3D " gdate +\"%s%6N\" ") | getline _), 
       close( __) ^ (RS =3D ___))_ =
  }
  function tim= er(_,__) { 
<= b>      return \
      +_ < (__=3D ep16())^(_<_) \
=       ?   __\
      := (__-_) /\
        ( ( (_+=3D_^=3D_<= _)+_*_*_)^(_ +_+  _)*\
=             ( _++^!++_ +    _^-(= _ +_+--_) ) )
  }=
  BEGIN {  __ =3D timer(_ =3D _<_)
      &nbs= p; OFMT =3D "%.25g" 
    CONVFMT= =3D "%.250g"
          _^=3D_=
  }  ($++NF =3D sprintf("%.13f", timer(__)))^!_ +\
     ($++NF =3D        lo= g( $_ ) / log(_+_))^!_' 

--------------= -------------------------------

timeout --fo= reground 1200 gfactor 49456902806087647575555655201
timeout= --foreground 1200 gfactor 244598523517080022888688284353651157229911632785= 2398350401

494569028060876475755556552= 01: 49456902806087647575555655201 0.0047909999999 95.3201585519276761715445= 90033590793609619140625


------=_Part_5154225_245599714.1669560496798--