log☇︎
158 entries in 0.377s
a111: Logged on 2017-08-14 17:57 asciilifeform: if instead of 'mult of 64' we had 'powers of 2', we could dispense with the odd split in karatsuba
asciilifeform: as for the other thing, right now we have a 'classical' karatsuba that permits odd splits
asciilifeform: recall also that, since we have karatsuba, cost goes up with W logarithmically, rather than quadratically
asciilifeform: if instead of 'mult of 64' we had 'powers of 2', we could dispense with the odd split in karatsuba ☟︎
asciilifeform: it would simplify many routines, in particular karatsuba
asciilifeform: recall, constanttime karatsuba did not (afaik) publicly exist before i posted it...
asciilifeform: there is not an equiv of karatsuba for it
asciilifeform: http://btcbase.org/log/2017-08-08#1695463 << i realized that this might not be true : the (empirically found, but seems to hold on all of my iron) threshhold for karatsuba +ev is > 8 words : ☝︎
asciilifeform: *karatsuba
ascii_modem: nao for karatsuba squaring case. and that's mostly it.
a111: Logged on 2017-07-15 13:00 asciilifeform: btw if you're actually doing something that doesn't need constanttime, you can simply put the obvious check-for-zero in the karatsuba and get 2-9000x boost for mul.
asciilifeform: btw if you're actually doing something that doesn't need constanttime, you can simply put the obvious check-for-zero in the karatsuba and get 2-9000x boost for mul. ☟︎
asciilifeform: i am considering including a karatsuba squaring case - for 2x speed boost; but that's definitely it.
asciilifeform: not built for speed. but for simplicity. the only concessions to optimization (karatsuba, etc) are strictly what was necessary to get to where rsa happens in merely annoying, rather than geological, time .
mod6: (contains completed karatsuba, but no comba)
a111: Logged on 2017-07-13 05:21 mod6: this is actually using karatsuba, haven't even integrated the new comba code yet.
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 ☝︎
mod6: this is actually using karatsuba, haven't even integrated the new comba code yet. ☟︎
mod6: yeah, just wanted to remember/remind myself of why we didn't use that, and looked at karatsuba instead, but then saw this again: http://btcbase.org/log/2017-05-21#1659981 ☝︎
asciilifeform: generalization of karatsuba, but pretty useless for fitsinhead rsatron imho
asciilifeform: same figure sans karatsuba : 3.7s.
a111: Logged on 2017-06-29 19:57 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
a111: Logged on 2017-06-21 16:44 asciilifeform: ( 8192bit exponentiation: ~10min with egyptological mul; 20.5s was with first-grade mul; 17.7 with karatsuba posted today )
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 ☝︎☟︎
mod6: this is outside the spec, but just as an experiment, what kinda timings do we get if you were to do inline asm for the W_Mul & Karatsuba procedures? is this worth doing?
asciilifeform: ( 8192bit exponentiation: ~10min with egyptological mul; 20.5s was with first-grade mul; 17.7 with karatsuba posted today ) ☟︎
asciilifeform: ( you physically cannot have karatsuba or anything of the kind if you cannot make FZs of several sizes. however the F remains, it is still impermissible to involve FZs of variant bitnesses in any arithmetical operation when invoking . )
asciilifeform: and, unrelatedly, karatsuba parallelizes (into 3 forks) without any substantial effort, so can also speed up whatever the bare bone speed ends up being, 3x
a111: Logged on 2017-06-18 23:30 asciilifeform: and realized, while doing this, that in fact you don't need 2k+2 bits for the karatsuba intermediates, you can do instead of (x0+x1)*(y0+y1) , (x0-x1)*(y0-y1), and then you don't need to propagate carries, but only take absolutevalue and xor the borrows to see if gotta invert the resulting term
a111: Logged on 2017-06-18 23:30 asciilifeform: and realized, while doing this, that in fact you don't need 2k+2 bits for the karatsuba intermediates, you can do instead of (x0+x1)*(y0+y1) , (x0-x1)*(y0-y1), and then you don't need to propagate carries, but only take absolutevalue and xor the borrows to see if gotta invert the resulting term
asciilifeform: and then i look in shitpile of paperz and find that some d00d actually did this, called it 'subtractive karatsuba', used in some microcontroller,
asciilifeform: and realized, while doing this, that in fact you don't need 2k+2 bits for the karatsuba intermediates, you can do instead of (x0+x1)*(y0+y1) , (x0-x1)*(y0-y1), and then you don't need to propagate carries, but only take absolutevalue and xor the borrows to see if gotta invert the resulting term ☟︎☟︎
asciilifeform: btw iirc this is an ~actual~ exercise in knuth -- to show that you still need karatsuba on a box where add(word,word) takes same time as mult(word,word)
asciilifeform: karatsuba et al weren't even working with computers. but wrestling with question of how much, abstractly, work, does multiplication per se entail.
mod6: yeah, few examples i've seen of karatsuba all use base 10..
mod6: I guess, it doesn't cover karatsuba specifically, but gives some background perhaps for the uninitiated.
asciilifeform: i'll review karatsuba here, ftr. suppose you have 2 L-bit numbers, X and Y, to multiply. you can multiply X*Y the usual way, is O(N^2). but instead anatoly alexeevich k. shows us that you can cut X into X0,X1, ceil(x/2) and floor(x/2) bits, respectively, and same to Y, -> Y0,Y1, and then you only gotta do THREE multiplications, X0*Y0, X1*Y1, (X0+X1)*(Y0+Y1)
asciilifeform: (fixed-space karatsuba)
ave1: From looking at karatsuba and how it could work bitwise, it might also be useful to have a starting offset
asciilifeform: *karatsuba
asciilifeform sat with notebook on the grass near usg capitol, good weather, and was aaalmost getting somewhere in re fixed-time karatsuba, when suddenly massive RUSSIA OUT OF UKRAINE!1111 troop of 'protesters', drums, правый сектор ( ukronazi!111 ) flagz, etc, etc , marched past.
asciilifeform is haunted by the notion that constant-time karatsuba gotta exist SOMEWHERE
asciilifeform: nao we need a non-recursive (! , SPARK won't allow recursion nor is it constanttimesafe to have any), constant-time karatsuba...
asciilifeform: probably doomed to karatsuba
a111: Logged on 2017-04-28 23:50 phf: in related lulz Karatsuba and Ofman's "Multiplication of Many-Digital Numbers by Automatic Computers" doesn't seem to be available anywhere online, but "everyone" seems to know it somehow
asciilifeform: http://www.mi.ras.ru/~karatsuba << subj.
phf: philistine that i am, for a longest time i thought karatsuba was japanese..
asciilifeform: ( karatsuba, that is. knuth afaik zombies along still. )
asciilifeform: phf: karatsuba's algo is in knuth
phf: in related lulz Karatsuba and Ofman's "Multiplication of Many-Digital Numbers by Automatic Computers" doesn't seem to be available anywhere online, but "everyone" seems to know it somehow ☟︎
ascii_field: normally, acca relies on sidechannels (e.g., karatsuba mult. timing)
assbot: Logged on 15-07-2014 03:00:27; asciilifeform: one of my first job interviews out of uni. telephone. a fellow from one of the giant gov. contractors was really intrigued that i know x86 asm., have reversed crud for money. i ask him 'what's the job'. he: automated reversing. me: of what. he: ever hear of karatsuba's algo? me: sure. bignum mult. him: well, we wanna find encryption softs on terrorist drives!
assbot: Logged on 15-07-2014 03:00:27; asciilifeform: one of my first job interviews out of uni. telephone. a fellow from one of the giant gov. contractors was really intrigued that i know x86 asm., have reversed crud for money. i ask him 'what's the job'. he: automated reversing. me: of what. he: ever hear of karatsuba's algo? me: sure. bignum mult. him: well, we wanna find encryption softs on terrorist drives!
assbot: 2 results for 'karatsuba anthem' : http://search.bitcoin-assets.com/?q=karatsuba+anthem
asciilifeform: !s karatsuba anthem
asciilifeform: one of my first job interviews out of uni. telephone. a fellow from one of the giant gov. contractors was really intrigued that i know x86 asm., have reversed crud for money. i ask him 'what's the job'. he: automated reversing. me: of what. he: ever hear of karatsuba's algo? me: sure. bignum mult. him: well, we wanna find encryption softs on terrorist drives! ☟︎☟︎
asciilifeform: benkay: what, Modified Karatsuba Anthem?
asciilifeform: '... the judge then ruled that the death of a keyholder at the hands of his fork is to be considered 'assisted suicide.' when he finished belting out the last verse of Modified-Karatsuba Anthem, his secretary drew her Nagant... '