asciilifeform: BingoBoingo: asciilifeform was 1 time 'lucky' enuff to find an edge case where gimp barfed and had to resort to a heathen photo editor on toilet box . ( stitching segments of photos that weighed GB+ , in the lispm reversing series. on very similar irons, the heathen proggy ran, gimp -- ground to halt. i suspect gimp has some o(n^2)-isms in it. )

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: the 'limiting reactant' speedwise is gcd ( o(n^2), see ch. 15. ) .

asciilifeform: constanttimeized stein's o(n^2) gcd ( http://www.loper-os.org/?p=2963 ) is not only imho fast enuff (even a magical 100fold speedup in it, would not affect speed of rsa key gen measurably , consider above ) but fits-in-head and has no error terms.

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

asciilifeform: mircea_popescu: it is certainly physically possible to do it that way, but the recognition is at best O(N^2) so one'd need some rather substantial irons; and also correspondingly moar sensitive to specks of dust in photo

asciilifeform: aha, recall the 'omfg flow graph is O(N^2)' thread

asciilifeform: ( 'how perverse the imposed model' is imho not a purely subjective statement -- and goes back to the 'orthogonality' discussion; if , as in the earlier thread, in your system adding a 'not' gate suddenly turns a o(n log n) op into a o(n^2), this is perverse, as there cannot be any mathematical justification for it, it is purely a result of braindamaged programmers

asciilifeform: this abolishes the o(n^2) cyclicity detector. which is not wholly unlike 'running marathon in gas mask'

asciilifeform: turning a dump truck full of ???!?$$??? that you found on the street, that contains some parts valid v-sigs, patches, and some parts chicken shit -- into a purely valid v-tree , is o(n^2). but q is why to permit the dump truck situation to begin with.

asciilifeform: mircea_popescu: nope. it was resolved in the correct way ('give the vtron the obvious hint , i.e. sanely named files , that turns the problem from o(n^2) into o(n)' )

asciilifeform: and division is O(N^2).

asciilifeform: the O(N^2) algos cost moar then.

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: O(N^2).

asciilifeform: pretty 'martian' algo for the usual O(N^2) mults, but notably it doesn't need a full Z's worth of temporary row space, but only 3 words' , ~regardless of Z width~ !

asciilifeform: basic idea is that k's algo transforms a N-bit O(N^2) mult, into instead ~three~ (N/2)-bit mults

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: unfortunately , per grandfather's pistol , a tx ~in~ a block can spend the output of another, in same block; so verification of block tx is O(N^2) but the N is the count of tx in the block.

asciilifeform: it is retarded and makes for 'orphanages' and O(N^2) verifications.

asciilifeform: O(N^2) verification suxxx.

asciilifeform: O(N^2) verification of each incoming block, is even worse of a 'heat death' rate than of traditional bitcoin

asciilifeform: in fact verification from-genesis is O(N^2) !

asciilifeform: danielpbarron: O(n^2) -- with orphanages etc. - tx verification-- suxx.

asciilifeform: in other languages, e.g., python, ruby, there is a lesser sin, you end up stuffing multitude of O(n) ops in places where you oughta have O(1), O(n^2) ops where with some thought you could've had O(n), etc. and the braindamage adds up

asciilifeform: ran in O(N^2).

asciilifeform: !#s O(N^2)

asciilifeform: iterating over patches is O(N^2) (unless the files are correctly named, patch.nickname.sig, which we do, but imho is a bit of a cheat)

asciilifeform: which is agonizingly O(N^2)

asciilifeform: 'This incentivization scheme is often called Child Pays For Parent (CPFP). In the simplest version, miners group a transaction and all of its ancestors together, calculating their total fee-per-byte in order to determine whether mining them together pays a high enough fee to outbid other individual transactions the miner wants to include in its next block.' << ain't that O(N^2) ?

asciilifeform: now it is O(N^2) process to learn why.

asciilifeform: you resolve in O(N^2).

asciilifeform: not doing so, gives you a worst-case of O(N^2) !

asciilifeform currently racking brain over how to make the thing verify in better than O(N^2)

asciilifeform: getting ~all~ the blocks is O(n^2)

asciilifeform: (e.g. what 'O(N)' or 'O(N^2)' means)

asciilifeform: erratum: where i wrote 'O(N^2)' ought to be O(N). complexity of fetching ~all~ blocks is O(N^2).