Hello everyone… I recently made a full precision addition operator project… Here it is.
I optimised it as much as I can, but on checking runtime growth for different digits addition, I noticed quadratic O(n^2) growth.
I believe it is the join string block which does that, maybe copying the whole string, only for adding each part.

I also added a simple “memo” optimization, but quickly understood that it wouldn't help much, and it didn't.

Are the scratch strings immutable? If yes, any method to bypass this bottleneck? Any help would be appreciated….

Also, I stumbled across this project by @odin123com549. It uses digit by digit calculation and directly uses string operations, without using lists at all (I am currently concerned only with addition) but still manages to get equal runtimes, if not faster.

Thanks and Regards,
Parle–G

JS string concatenation is supposed to be really efficient. Your code is linear time if you just drop the part to construct the output string, right? Of course you could just use lists for arguments and output (only converting to a string for user display), but in Scratch that comes with its own difficulties…

Thanks for the reply…

While it's true that is string concatenation is efficient, I speculate that scratch blocks have substantial overhead, which is messing with JS' theoretic approach. I understand that using lists for operations subsequent to the assembly might be a good option…
(I say might because coding list operations are another hassle… But maybe it could help with place-value aided operations? )

Also, why is @odin123com549's project calculating at approximately the same speed as mine? He is using base-10, compared to my “base-9” , which shall (?) be doing 9x more calculations than mine (or I think so…)

His/her code for reference:

define (a) + (b)
set [a index v] to (length of (a::custom)::operators)
set [b index v] to (length of (b::custom)::operators)
set [carry v] to [0]
set [result v] to []
repeat until <<<(a index) \< [1]> and <(b index) \< [1]>> and <(carry) = [0]>>
    set [num v] to (((letter (a index) of (a::custom)) + (letter (b index) of (b::custom))) + (carry))
    set [result v] to (join ((num) mod (10)) (result))
    set [carry v] to ([floor v] of ((num) / (10))::operators)
    change [a index v] by (-1)
    change [b index v] by (-1)
end

Total work = n^2/2 (approx, neglect n/2)

Here is my code:

define str.add (num1) (num2)
set [iA v] to (length of (num1::custom)::operators)
set [iB v] to (length of (num2::custom)::operators)
set [str.cbit v] to [0]
delete all of [str.mid v]
set [str.out v] to []
repeat until <<(iA) \< [1]> and <(iB) \< [1]>>
    set [str.init v] to ((iA) - (8))
    if <(str.init) \< [1]> then
        set [str.init v] to [1]
    end
    set [fA v] to []
    set [j v] to (str.init)
    repeat (((iA) - (str.init)) + (1))
        set [fA v] to (join (fA) (letter (j) of (num1::custom)))
        change [j v] by (1)
    end
    set [iA v] to ((str.init) - (1))
    set [str.init v] to ((iB) - (8))
    if <(str.init) \< [1]> then
        set [str.init v] to [1]
    end
    set [fB v] to []
    set [j v] to (str.init)
    repeat (((iB) - (str.init)) + (1))
        set [fB v] to (join (fB) (letter (j) of (num2::custom)))
        change [j v] by (1)
    end
    set [iB v] to ((str.init) - (1))
    set [str.sum v] to (((fA) + (fB)) + (str.cbit))
    set [str.cbit v] to ([floor v] of ((str.sum) / (1000000000))::operators)
    set [str.seg v] to ((str.sum) mod (1000000000))
    if <<(iA) \> [0]> or <(iB) \> [0]>> then
        repeat ((9) - (length of (str.seg)::operators))
            set [str.seg v] to (join [0] (str.seg))
        end
    end
    add (str.seg) to [str.mid v]
end
if <(str.cbit) \> [0]> then
    add (str.cbit) to [str.mid v]
end
set [i v] to (length of [str.mid v]::data)
set [str.memo v] to []
repeat (i)
    set [str.memo v] to (join (str.memo) (item (i) of [str.mid v]))
    change [i v] by (-1)
    if <((i) mod (50)) = [0]> then
        set [str.out v] to (join (str.out) (str.memo))
        set [str.memo v] to []
    end
end
set [str.out v] to (join (str.out) (str.memo))

Total work = n^2/18 (approx, neglect n/2)

So, is it the overhead which is causing my program to slow down?
…

Also, on checking the runtime in my project for the first few thousand digits, it scaled somewhat linearly… E.g. 0.524s for two 100k digits, and 1.017s for 200k digits. Why?? (It's a bit strange, or so I think, because at 100k, 200k digits, the “quadratic effect” should not be negligible…)
…

Is append faster than prepend in scratch too?

(join [...] [new string])//append

(join [new string] [...])//prepend

Which is faster? “join(…)(n characters)” carried out one time, VS “join(…)(one character)” repeated n times
(Or maybe there is an optimal balance between no. of characters and repetitions? Or nested join?)

Is append amortised O(1) and prepend O(n) , or are both O(n)? I guess scratch strings are immutable…
Also, about list operations, isn't “add item to list xyz” block O(1) too?
Why then, they create too much overhead, causing my program to slow down?
…

Also is there any other optimization that I'm missing?
…

I think of binary join (after pair-handling) , where

• I join item 1 & 2, item 3 & 4, …. item n-1 & n resulting in n/2 strings.
  
• I join pair 1 & 2, pair 3 & 4, …. pair n/2 -1 & n/2 resulting in n/4 strings.
  
• … and so on, till I get one long string?
  

Sorry for the long blabbery, but I would really appreciate if someone can help me out…

Thanks and Regards,
Parle–G