mircea_popescu: so im trying out being 70s, what. do you want me to go in unaware, end up surprised by it ?
jhvh1: BingoBoingo: Bitstamp BTCUSD last: 4350.03, vol: 5177.09336958 | Bitfinex BTCUSD last: 4359.5, vol: 16987.47514348 | BTCChina BTCUSD last: 4229.3316, vol: 0 | Kraken BTCUSD last: 4359.5, vol: 2319.21013539 | Volume-weighted last average: 4357.49756913
mod6: btw, do you have a simple test harness setup for this just to assert some known output values?
mod6: i think ima make a quick one for myself just so i can see what youre sayin on stuff like that.
a111: Logged on 2017-10-02 19:31 asciilifeform: note also that the calling style from early versions will not work, there is no longer a .Z , FZ is not a struct any moar, it is just a word array
mod6: aha, one similar to that. although, indeed, that works too.
mod6: i'd like to also maybe make some unit tests around your procedures/functions.
mod6: im basically going to have to do this anyway -- this helps "fitting in mod6
mod6: ah, ok. and yah, no need to let p out of the garage until ffa is pretty much "there".
mod6: mainly, I read through them. because, there's still a lot for me to grok here. and it's easy to fool oneself into groking if you treat it like a blackbox instead of actually reading the code.
mod6: (other than the ffa-fact, which i use sometimes to try new, whole, ffa parts out)
mod6: yeah, something simple like this is a good starting spot.
mod6: sweet. is pretty interesting tho.
mod6: ahh, right. i recal.
mod6: <+asciilifeform> out of curiosity, how long the py item takes on mod6's box ? << was just saving... lemme give it a try here. want me to try it on the i5/8gb box ?
mod6: grabbed 3 runs for good measure
phf: (3s on python, 9s on cmucl, 1.2s on sbcl)
mod6: (fwiw, that machine I just ran it on has Python 2.7.9)
mod6: im gonna try it on the build-donkey box, core2duo/4gb
mod6: and same version of py there too. ok just a sec.
shinohai: Anyone have the lisp version handy?
phf: asciilifeform: wait, that seems like a cheap sleight of hand. obviously increasing number of iterations in an iterative algorithm that you gave is going to increase run time
mircea_popescu: phf his point is that if you're going to compare fixtime with something else, better make sure you get a long case in there too.
phf: mircea_popescu: well he either has a constant time algorithm in ffa, in which case if the goal is to compare speed specifically we should be comparing fixtime ffa and fixtime something else. otherwise he has a variable time algorithm running at worst case constant time, in which case the comparison is between base operation speed, which is still going to come out on top
phf: i guess the point of this exercise is to show that iteration sizes further leak timing information
mircea_popescu: you're not having any of this new fangled "constant time ~= fixedtime ie, variable time running at worst case" ?
phf: well, it's conveniently two strategies: closed form solutions and constant iterators. if you don't have a closed form solution, you have to iterate, which you simply do at the upper bound constraint by a data type size. i don't see how theoretically it can be anything else
shinohai: I get 0m1.236s using sbcl (i5)
phf: i suspect that ffa's take on expmod is to iterate over every bigit of the exponent, which will have to perform base operations no matter what the numeric size is, but that's a guess.
phf: i'm trying to figure it out from first principles :) (i haven't had time to look at the recent, i.e. past month, versions yet)
mircea_popescu: my guess is that it's as close to closed form solutions as possible, hence all the barrett fucking etc, but then again i'm a weak programmer and a very dubious mathematician.
a111: Logged on 2017-10-07 16:49 mircea_popescu: my guess is that it's as close to closed form solutions as possible, hence all the barrett fucking etc, but then again i'm a weak programmer and a very dubious mathematician.
a111: Logged on 2017-10-07 16:26 phf: asciilifeform: wait, that seems like a cheap sleight of hand. obviously increasing number of iterations in an iterative algorithm that you gave is going to increase run time
a111: Logged on 2017-10-07 19:28 asciilifeform:
http://btcbase.org/log/2017-10-07#1722358 << point was exactly to compare like items. i.e. heathendom does NOT get to 'win' by 'oh hey the hamming weight of exponent is only 2, not 4096, so we only do 4 modexps and not 8192'
deedbot: apeloyee voiced for 30 minutes.
jhvh1: apeloyee: The operation succeeded.
apeloyee: asciilifeform: turns out a simple, ffa-suitable O(N^2) algorithm exists for GCD. This is adapted from GMP docs with one extra operation in the loop:
http://p.bvulpes.com/pastes/oupUJ/?raw=true . Note: the code as posted is likely wrong, but I'm sure the idea can be made to work.
apeloyee:
http://btcbase.org/log/2017-10-07#1722289 << and the point of doing karatsuba is? you do 2 recursive calls to Mul_Karatsuba_TopOnly and one to Mul_Karatsuba. should've simply calculated upper_part(XLo*YHi), upper_part(YLo*XHi) and XHi*YHi
apeloyee: the multiply-by-approximate quotient in barrett's also needs only the lower part (plus 2 extra bits to the left), and lower part of product can be computed exactly (since rounding is not a problem)
deedbot: apeloyee voiced for 30 minutes.
a111: Logged on 2017-10-05 19:38 asciilifeform: want to gcd(candidate, biggestprimorialthatfitsintheffabitness)
apeloyee:
http://btcbase.org/log/2017-10-05#1721485 << alternatively, can *construct* numbers which don't have very small factors. pick a nonzero remainder mod 2, mod 3, ... mod largest-prime-fit-in-your-primorial and find what number of primorial is congruent to it using chinese remainder theorem
a111: Logged on 2017-10-05 19:38 asciilifeform: want to gcd(candidate, biggestprimorialthatfitsintheffabitness)
apeloyee: *what number has such remainder from division by 2,3, ...
apeloyee: the primorial has to be, say, 2^32 times less than the ffa maxint. then you can add randomnumber*primorial, and such a number is equally likely to any prime from some interval
ben_vulpes: danielpbarron: wouldja mind sharing that stage3 you build your eulora gentoos with?
a111: Logged on 2017-10-07 19:30 asciilifeform: i also suspect that they are in fact slower for maxhammingweight case of exponentiation and modulus, vs ffa.
phf: a whole new bignum that is
a111: Logged on 2017-10-07 19:28 asciilifeform:
http://btcbase.org/log/2017-10-07#1722358 << point was exactly to compare like items. i.e. heathendom does NOT get to 'win' by 'oh hey the hamming weight of exponent is only 2, not 4096, so we only do 4 modexps and not 8192'
a111: Logged on 2017-10-07 21:53 apeloyee: the primorial has to be, say, 2^32 times less than the ffa maxint. then you can add randomnumber*primorial, and such a number is equally likely to any prime from some interval
a111: Logged on 2017-10-07 21:09 apeloyee: asciilifeform: turns out a simple, ffa-suitable O(N^2) algorithm exists for GCD. This is adapted from GMP docs with one extra operation in the loop:
http://p.bvulpes.com/pastes/oupUJ/?raw=true . Note: the code as posted is likely wrong, but I'm sure the idea can be made to work.
a111: Logged on 2017-10-07 21:14 apeloyee:
http://btcbase.org/log/2017-10-07#1722289 << and the point of doing karatsuba is? you do 2 recursive calls to Mul_Karatsuba_TopOnly and one to Mul_Karatsuba. should've simply calculated upper_part(XLo*YHi), upper_part(YLo*XHi) and XHi*YHi
a111: Logged on 2017-10-07 21:25 apeloyee: the multiply-by-approximate quotient in barrett's also needs only the lower part (plus 2 extra bits to the left), and lower part of product can be computed exactly (since rounding is not a problem)
a111: Logged on 2017-10-07 21:48 apeloyee:
http://btcbase.org/log/2017-10-05#1721485 << alternatively, can *construct* numbers which don't have very small factors. pick a nonzero remainder mod 2, mod 3, ... mod largest-prime-fit-in-your-primorial and find what number of primorial is congruent to it using chinese remainder theorem
a111: Logged on 2017-08-14 16:14 asciilifeform: ( tldr : superiority of the FUCKGOATS-enabled approach, of get-new-N-bits-from-rng-then-primalitytest-until-done, vs the kochian get-N-bits-then-increment-until-passes-millerrabin )
a111: Logged on 2017-10-07 21:53 apeloyee: the primorial has to be, say, 2^32 times less than the ffa maxint. then you can add randomnumber*primorial, and such a number is equally likely to any prime from some interval
a111: Logged on 2017-10-07 22:39 phf:
http://btcbase.org/log/2017-10-07#1722379 << this is probably true but only because ffa mutates an array of bigits, where's any language level bignum system produces a whole new one for each operation
a111: Logged on 2017-10-07 16:42 shinohai: I get 0m1.236s using sbcl (i5)
a111: Logged on 2017-07-03 14:46 phf: i think ascii already made that point, that if you're profiling lisp with the vm startup, then you should also profile c machine from boot time. at the very least the vm should be warmed up by loading all the dependencies into the core, doing save-lisp on it, and then making sure that your foo.lisp has an up to date fasl. inside lisp though to achieve the optimizations you run variants of your function inside (time ...) until you bring it within the ra
mats: l0l an amzn frontend engineer friend has to work all through christmas week, got his vacation request denied by upper mgmt
mats: he put it in almost four months in advance and still can’t take a few days off
BingoBoingo: Well, he works in the retail industry. What should he expect?
a111: Logged on 2017-10-08 00:16 asciilifeform: the ONLY correct method of generating cryptoprimes, is to 1) get N bits from FUCKGOATS 2) determine, in fixed spacetime every single time, whether that string of bits constitutes a usable prime.
mircea_popescu: having a primorial at the ready to exclude a large number of common (ie, low) factors in one single gcd likely speeds this up significantly.
a111: Logged on 2017-10-08 00:24 asciilifeform: so no, nobody is replacing miller-rabin with gcd(primorial, x).
mircea_popescu: recall diana_coman 's trick of "multiply by 6" ? pretty much the inverse of the same idea.
mircea_popescu: yes, but then would you rather 999 r-m or 995 primorial gcd and 4 r-m ?
a111: Logged on 2017-10-08 01:35 mircea_popescu: having a primorial at the ready to exclude a large number of common (ie, low) factors in one single gcd likely speeds this up significantly.
a111: Logged on 2017-08-14 17:15 asciilifeform: idea is, for pre-millerrabin litmus, take gcd(candidate, Qw) where Qw is largest primorial that fits in the ffawidth
mircea_popescu: incidentally, if looking for 4096 bit prime wouldn't the correct approach be to take 4094 bits of rng and glue 1 on either end ?
mircea_popescu: as no 0 led or 0 terminated string will ever pass anyway
shinohai: TOP KEK "Anonymous access through tor browser"!!!!
shinohai: They even bothered to vanitygen a custom tor addy