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 15:42:54 -0700 Organization: A noiseless patient Spider Lines: 133 Message-ID: <86v797124x.fsf@linuxsc.com> References: <115eks4$3pn1s$1@dont-email.me> <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> <86zeyj1lrw.fsf@linuxsc.com> <20260818221740.00002511@yahoo.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Date: Tue, 18 Aug 2026 22:42:59 +0000 (UTC) Injection-Info: dont-email.me; logging-data="2329445"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/c9AbwD7M5E7cG4Mng9U6CziXpy9RNth0="; posting-host="ca9ea2dc1c21634b0183d24df1683dd8" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:AdYk69xZPf4Giyah7S9JNyhqSkM= sha1:tTfI8F9DqSeia66odKSj6zPTkQY= sha256:bKExmzx7FLI4KeWDu7ciRZbRe3wM4HrhHHeqSja6OSc= sha1:TkukgKywX7dT5OkrUk62Q4S2p7M= sha256:89sPLAIu0pHx6nhO41IdReOhUuIht2A303131YBXXqo= Xref: csiph.com comp.lang.c:401313 Michael S writes: > On Tue, 18 Aug 2026 08:38:43 -0700 > Tim Rentsch wrote: > >> 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. > > In my real world case the target was 32-bit microcontroller-class > soft core without hardware multiplier running at 100 MHz. Also, > we should not forget that a single ECDSA signature validation > contains plenty of ipow() steps. Right now I don't remember how > many. > > I didn't try algorithm presented here by Bart, but tried something > that can be seen as its mirror image. > > wword ipow(wword a, wword n) > { > if (n < 2) > return n == 0 ? 1 : a; > > wword y = ipow(a, n/2); > y *= y; > if (n & 1) > y *= a; > return y; > } > > Please, treat it as a pseudocode. > Real code was more complicated, with function calls instead of * > and recursion was manually converted to iteration. Huh. An unusual way of handling the recursive nature of the problem. It's not obvious to me how it works exactly. > The result was slower than the following (pseudo) code: That isn't surprising, considering that the recursive call is not tail recursive. > wword ipow(wword a, wword n) > { > wword y = 1, p = a; > while (1) { > if (n & 1) > y *= p; > n /= 2; > if (!n) > break; > p *= p; > } > return y; > } > > I didn't try to investiagete reasons for the difference. If I were to take a similar approach, I might write something like this (disclaimer: not compiled): wword xpow( wword a, wword n ){ if( n < 2 ){ // handle powers less than 2 // exercise for the reader } wword r = 1; do { if( n & 1 ) r *= a; a *= a; } while( n /= 2, n > 1 ); return r*a; }