#asciilifeform | 2020-01-04

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]

01:56

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.

~ 40 minutes ~

02:36

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

~ 1 hours 13 minutes ~

03:50

Apocalyptic: i was speaking of gcd ~per se~ rather than the given algo

03:51

afaik no one knows what the ~intrinsic~ complexity of gcd is .

03:54

( 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 )

04:00

*

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

04:09

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 )

04:11

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.

04:15

most egregiously famous example of this kinda thing is prolly 'aks' primality litmus.

04:15

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

~ 5 hours 18 minutes ~

09:33

feedbot

http://ossasepia.com/2020/01/04/notes-on-computer-graphics-transfer-vs-display/ << Ossa Sepia -- Notes on Computer Graphics - Transfer vs. Display

~ 2 hours 59 minutes ~

12:32

asciilifeform, I see, nice thread with apeloyee

~ 1 hours 48 minutes ~

14:21

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

~ 3 hours 29 minutes ~

17:50

adlai: 1btc. i never hedged on bitbet but i have doubled down

18:00

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

18:08

and ofc people being too ashamed to confess over voice

18:12

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

~ 1 hours 10 minutes ~

19:22

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.

19:29