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

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

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

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

• 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?
  

Parle--G wrote:

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.

    join (args) {
        return Cast.toString(args.STRING1) + Cast.toString(args.STRING2);
    }

Is append amortised O(1) and prepend O(n) , or are both O(n)? I guess scratch strings are immutable…

comp09 wrote:

It depends on the JavaScript engine, but string concatenation in JavaScript is not necessarily not constant time.

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?
  

P.S. - On an unrelated note, does anyone know how to write mathematical notation in the Scratch forums? I need to show some facts and workings related to my project, which requires the ability to display symbols like summations (Σ), matrices, and other technical notation…

Parle--G wrote:

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

Parle--G wrote:

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

 * To improve performance of common operations, the following optimizations are
 * made which affect the engine's representation of strings:
 *
 *  - The plain vanilla representation is a "linear" string which consists of a
 *    string header in the GC heap and a malloc'd char array.
 *
 *  - To avoid copying a substring of an existing "base" string , a "dependent"
 *    string (JSDependentString) can be created which points into the base
 *    string's char array.
 *
 *  - To avoid O(n^2) char buffer copying, a "rope" node (JSRope) can be created
 *    to represent a delayed string concatenation. Concatenation (called
 *    flattening) is performed if and when a linear char array is requested. In
 *    general, ropes form a binary dag whose internal nodes are JSRope string
 *    headers with no associated char array and whose leaf nodes are linear
 *    strings.
 *
 *  - To avoid copying the leftmost string when flattening, we may produce an
 *    "extensible" string, which tracks not only its actual length but also its
 *    buffer's overall size. If such an "extensible" string appears as the
 *    leftmost string in a subsequent flatten, and its buffer has enough unused
 *    space, we can simply flatten the rest of the ropes into its buffer,
 *    leaving its text in place. We then transfer ownership of its buffer to the
 *    flattened rope, and mutate the donor extensible string into a dependent
 *    string referencing its original buffer.
 *
 *    (The term "extensible" does not imply that we ever 'realloc' the buffer.
 *    Extensible strings may have dependent strings pointing into them, and the
 *    JSAPI hands out pointers to linear strings' buffers, so resizing with
 *    'realloc' is generally not possible.)
 *
 *  - To avoid allocating small char arrays, short strings can be stored inline
 *    in the string header (JSInlineString). These come in two flavours:
 *    JSThinInlineString, which is the same size as JSString; and
 *    JSFatInlineString, which has a larger header and so can fit more chars.
 *
 *  - To avoid comparing O(n) string equality comparison, strings can be
 *    canonicalized to "atoms" (JSAtom) such that there is a single atom with a
 *    given (length,chars).

(join [] [])

Was I wrong to suspect O(n^2) ?