asciilifeform: mp_en_viaje: i recall finding that comba died right when was writing comba's algo.

asciilifeform: ( properly speaking, comba aint even a mult algo in the usual mathematical sense, but merely a 'sideways' restatement of the traditional schoolboy O(n^2) mult algo to behave smoother on pc and other irons where cache is in play )

asciilifeform: bvt: what i meant is, the optimal asmistic base case is not necessarily comba. could be 'micro' karatsuba, or even straight schoolbook mul. for so long as asm.

asciilifeform: bvt: it isn't actually a given that comba is even needed at all, with asmistic 64x64 mul

asciilifeform: !Q later tell phf plox to snarf sig in http://bvt-trace.net/2019/05/unrolled-assembly-comba/ ( and diana_coman 's earlier ) at your earliest , into btcbase, ty

asciilifeform: http://bvt-trace.net/2019/05/unrolled-assembly-comba/#selection-93.193-97.1

asciilifeform: !Q later tell bvt http://bvt-trace.net/2019/03/ffa-chapter-9-homework-comba-in-x86_64-assembly/comment-page-1/#comment-12

asciilifeform: i found last yr, for instance, that unrolled comba ( still in ada ) gives 20-25% speedup.

asciilifeform: a correct asmism would simply read the carry flag and put the value where it belongs (e.g. in fz_add, into the next addition, in comba -- into the accumulator; etc)

asciilifeform: in a hypothetical asmistic branch of ffa, you'd want to implement whole comba in asm, rather than merely word mul

asciilifeform: the remaining virgin land for speed revvup, is asmism for base cases. ( and ~possibly~ in combination with unrolled comba )

asciilifeform: bvt: comba itself ended up on the list of things that made it in by very small margin ( it wins perhaps 10%, on most pc iron , vs straight word*word mul as base case, try it yourself by turning the threshhold knob )

asciilifeform: bvt: there's a long list of things that asciilifeform considered and (for time being) rejected from ffa, on acct of costing substantial complexity for very small saving of cpu cost. e.g. unrolled comba.

asciilifeform: 'locality' effect is actually why e.g. comba wins over ordinary 'kindergarten' o(n^2) mult

asciilifeform: errything after, will be linear (e.g. asm mul, in the end, unrolled comba, etc)

asciilifeform: mircea_popescu: iirc just comba (basecase mul) alone, if asmified, is 8x speedup , even if all else left alone

asciilifeform: i had example of this back in august, of comba.

asciilifeform: the use of comba , and in fact of ANY multiplier that compiles into having a x86 MUL instruction anywhere in it, is unsafe on intel celeron. and ppc32. and possibly ppc64.

asciilifeform: mircea_popescu: apparently not. hence why unrolled comba was iirc 2x+ speedup

asciilifeform: i got a megatonne of those . ( e.g. unrolled comba )

asciilifeform: ... pretty depressing, and just about obscene, you could just about fit msdos mega-game DIGGER.COM in the space taken by gcc's notion of ffa_mul_comba !

asciilifeform: trinque: but let's say i take a routine from earlier ( e.g. unrolled comba mult ) and the rest -- from last week's

asciilifeform: ( i already have, and posted, an unrolled comba -- see august log. )

asciilifeform: i'ma also try unrolled comba, to compare, but do not want to spend eons on this type of massage, it can happen after release of p.

asciilifeform: unrolled comba is here: http://btcbase.org/log/2017-08-10#1696236 ( http://archive.is/iMI4W ) ☝︎

asciilifeform: i still think that it makes sense to do this only after every other bolt is as tight as physically possible -- bernsteinian karatsuba, unrolled comba, etc

asciilifeform: ( unrolled comba would have explicit unrolled cases for 1,2,...,8-word operands )

asciilifeform: for instance unrolled comba wins 20-25% speed, but i did not use it in place of the generic because it is longer and harder to read.

asciilifeform: incidentally ~95% of the work ffa does in modexp, now, is multiplication. which means that there is further 20-25% speedup waiting to be had when i get bernsteinian optimization for karatsuba ( haven't yet figured it out, he buried it deep in a paper , as if he were an alchemist, quite cryptically ) and another 10-20% optimization if we move to unrolled comba ( see august thread. )

asciilifeform: will need asymmetric comba, too...

asciilifeform: it was about 100x slower than comba ( current basecase ) and ~150x slower than karatsuba+comba ( currently what we use )

asciilifeform: the way the comba multer works

asciilifeform: ( one answer is that at the very bottom of the barrel, where karatsuba hits the basecase comba mult, we permit division )

asciilifeform: also lit search came back with an equally obscure recipe for a 10% or so faster comba ( tldr : compute the square (diagonal) digits in a separate walk, and add them to the result of the nondiagonal pass , at the end )

asciilifeform: forcing 2^x = W, x in Z , also simplifies comba

asciilifeform: we definitely don't need any case of comba above 8 tho

asciilifeform: for simplicity, tested the case that actually happens in practice: on a 64bit box, any ffa width over 512 bits gives a strictly 8-wide comba mult ocurrence ☟︎

asciilifeform: now wouldja believe i spent 3 wks trying to eliminate the if N mod 2 = 0 ... condition in Square_Comba

asciilifeform: it thereby follows that i could unroll comba into explicit cases from 1 to 8 words ☟︎

asciilifeform: in other noose, mod6 , phf , et al : http://btcbase.org/log/2017-07-10#1681208 nao 1.5s . ( this with karasbuba-squaring used in exp, and comba-squaring used as base case in the former. ) ☝︎☟︎

asciilifeform: http://btcbase.org/log/2017-07-13#1682308 << comba is an O(N^2) multer. it beats the classical one simply because it doesn't need a scratch buffer of length N. it goes as the base case in karatsuba, not instead of it ☝︎

asciilifeform: !#s comba

asciilifeform: ( alert reader will ask, what did i change ? answer : 1) comba 2) gcc -O2 (this keeps all bounds checks and dun do anything aggressive, just peepholes) )

asciilifeform: in other noose ! nao we have comba's algo multiplier as basecase in karatsuba (currently threshold 8 words) , and http://btcbase.org/log/2017-06-21#1673165 becomes now 7.5sec ☝︎☟︎

asciilifeform: in other sads, it turns out that paul g. comba ( of comba's multiplication algo ) died in april. ☟︎