feedbot: http://bingology.net/2020/peso-watch-tourism-season-edition/ << Bingology - BingoBoingo's Blog -- Peso Watch - Tourism Season Edition
Apocalyptic: http://logs.nosuchlabs.com/log/asciilifeform/2020-01-03#1004795 << I assume you mean the iterative version named algo 2 in [http://www.loper-os.org/?p=2963]
snsabot: Logged on 2020-01-03 22:59:55 asciilifeform: in the particular case of gcd, interestingly , i know of no proof that it is intrinsically o(n^2) in its worst case. but presently i conjecture that it is.
Apocalyptic: first it's trivial that every loop is O(n); assume a > b, if |a - b| <= b/2 then you decrease your next loop's smallest input by 1 bit, otherwise |a - b| > b/2 implies min(a,b) = b < 2a/3 so you lose log(3/2)/log(2) ~ 0.58 bits, the worst case is therefore 2n such loops
asciilifeform: Apocalyptic: i was speaking of gcd ~per se~ rather than the given algo
asciilifeform: afaik no one knows what the ~intrinsic~ complexity of gcd is .
asciilifeform: ( re the ~concrete~ algos in ffa -- for each of them it is quite easy to determine the complexity, because where there is iteration, its count depends strictly on the ~bitness~ of the input, and never on the input per se )
asciilifeform spent very little time attempting to find a sub-quadratic constant-spacetime algo for gcd, because gcd aint any kind of bottleneck in rsa or any cryptosystem i know of
asciilifeform: e.g. jebelean's gcd gives, theoretically, o(n^2 / log n) worst case, but at the cost of substantial overhead ( and massive lookup table )
asciilifeform: i put it in same garbage bin as e.g. fuhrer's method for multiplication. i.e. useful for outlandishly large (multi-MB) integers, but not for rsa or any other extant cryptosystem.
asciilifeform: most egregiously famous example of this kinda thing is prolly 'aks' primality litmus.
snsabot: (trilema) 2017-10-08 asciilifeform: i'm not aware of a fully deterministic test that doesn't run in geological (e.g. saxena) time
feedbot: http://ossasepia.com/2020/01/04/notes-on-computer-graphics-transfer-vs-display/ << Ossa Sepia -- Notes on Computer Graphics - Transfer vs. Display
Apocalyptic: asciilifeform, I see, nice thread with apeloyee
Apocalyptic: I'm sure you're aware of successive fibonacci numbers being the worst case in euclidean gcd, and indeed runs in n^2, but as to intrinsic gcd across all possible implementations I have no idea as well
mats: adlai: 1btc. i never hedged on bitbet but i have doubled down
mats: i did ok on the last potus prop based on suspicions statisticians were wrong about net based polls being beset by bot fraud and consequently less reliable than phone polling, after brexit
mats: and ofc people being too ashamed to confess over voice
mats: figured it would come down to a coin flip instead of 30/70, and with the odds so good it was obviously worth a shot. just wish i had pushed all my chips in rather than treating it as idiot insurance
asciilifeform: mats: i on other hand had put odds of lee sidol win at ~100%. and pushed ~all chips... cured me permanently of desire to bet on anyffin i hadn't personally rigged.
asciilifeform: mats: maybe i'ma a philistine, but will admit that i don't miss bbet.
feedbot: http://qntra.net/2020/01/civil-unrest-in-france-continues-as-macron-regime-remains-unpopular-usg-still-uninterested-in-this-low-hanging-regime-change-fruit/ << Qntra -- Civil Unrest In France Continues As Macron Regime Remains Unpopular, USG Still Uninterested In This Low Hanging Regime Change Fruit
feedbot: http://bingology.net/2020/data-protection-journey-part-2-add-more-heat/ << Bingology - BingoBoingo's Blog -- Data Protection Journey Part 2: Add More Heat