Path: csiph.com!eternal-september.org!feeder.eternal-september.org!nntp.eternal-september.org!.POSTED!not-for-mail From: Tim Rentsch Newsgroups: comp.lang.c Subject: Re: why is there not a ipow version of pow? Date: Tue, 18 Aug 2026 08:38:43 -0700 Organization: A noiseless patient Spider Lines: 59 Message-ID: <86zeyj1lrw.fsf@linuxsc.com> References: <115eks4$3pn1s$1@dont-email.me> <115f20j$3un9e$1@dont-email.me> <115f64m$ml3$1@raubtier-asyl.eternal-september.org> <115f7h5$1659$2@dont-email.me> <115f7v8$1b5d$1@raubtier-asyl.eternal-september.org> <115facm$1659$3@dont-email.me> <115favq$2ckl$1@raubtier-asyl.eternal-september.org> <115fe3u$1659$5@dont-email.me> <115feje$3nf1$1@raubtier-asyl.eternal-september.org> <115ffag$1659$9@dont-email.me> <115g94d$2pb62$1@paganini.bofh.team> <115h9mb$kpdk$1@dont-email.me> <115hjka$o7k2$1@kst.eternal-september.org> <20260812224333.000065c4@yahoo.com> <115im0c$136js$1@kst.eternal-september.org> <20260813002409.00003f1d@yahoo.com> <115ippl$15jbt$1@dont-email.me> <86lda740ix.fsf@linuxsc.com> <20260815231716.00002b94@yahoo.com> <868q643ccm.fsf@linuxsc.com> <20260818003501.00002080@yahoo.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Date: Tue, 18 Aug 2026 15:38:45 +0000 (UTC) Injection-Info: dont-email.me; logging-data="2046333"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+xb0dxFyviczDP9QdXZ7WRAH6HEySELYs="; posting-host="ca9ea2dc1c21634b0183d24df1683dd8" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:roYstbKCKqX+e3kZrEP+0k7etpA= sha1:vJIczwhSJycyItnu0QETU40yhmI= sha256:TPn90P3NHQYnwO9HZwUWeO9GLIn00fKWSAmW0nD0rJk= sha1:15l7wLuMZJVN6AgTdO7EP7Lb4Ug= sha256:vbBK/q1U2Y3vdbH566lZ6bItlcr27r+UMONAaF5SXNg= Xref: csiph.com comp.lang.c:401298 Michael S writes: > On Mon, 17 Aug 2026 10:07:05 -0700 > Tim Rentsch wrote: > >> Michael S writes: >> >>> On Sat, 15 Aug 2026 13:00:22 -0700 >>> Tim Rentsch wrote: >>> >>>> Lynn McGuire writes: >>>> >>>>> I have found over the years that 200 points seems to be best >>>>> when performing a numerical integration of a curve. For me, >>>>> 200 points is the point where diminishing returns has set in. >>>>> Of course, YMMV. >>>> >>>> Surely that depends on which integration method is being used. >>> >>> That is smaller of my troubles with this post of Lynn. >>> The bigger trouble is that my post, to which he "answered" did >>> not talk at all about integration. >> >> Yeah. Not too surprising really, considering the general level >> of the discussion -- an overly long thread for a problem that >> should take at most 15 minutes to solve just by writing an >> ipow() function. > > Performance of ipow() is quite important in Elliptic Curve > Cryptography (ECC). In this field it's worth spending much more > than 15 minutes on optimization of this core primitive. > Of course, in case of ECC integers are wider than 64-bit (although > not dramatically wider, IIRC, 192 bits are considered good enough > in many real-world applications) and arithmetic is modular. For the function originally being asked about, where the operations are being done on basic integer types, I think 15 minutes (or so) should be enough. For applications like Elliptic Curve Cryptography, where the values are multiple-precision integers rather than basic integer types, the same algorithm should be okay, except that attention needs to be given to the (modulo-ized) multi-precision multiplications used. The bottleneck is multiplications, not the overall algorithm structure. As an experiment I took the C implementation I first wrote (which had taken five or ten minutes) and wrote the same algorithm in python, except that multiplications were done mod 2**192. I ran trials with that, including for example >>> ipow( 97, 33333333333333333333333333333333333333333333333333333333333 ) 5528880020554650661730432042596473300798439881536715294689 All the trial invocations returned instantly. So I don't think the original basic algorithm needs to be changed; as long as care is given to how the multiplications are done (which python does a fair job at, for this size of operands), a simple implementation should be okay even for applications like ECC.