Nicolas Cellier uploaded a new version of Collections to project The Trunk:
http://source.squeak.org/trunk/Collections-nice.827.mcz

==================== Summary ====================

Name: Collections-nice.827
Author: nice
Time: 27 April 2019, 10:34:08.261332 pm
UUID: 6dd69760-fdb4-4e8c-8809-38a4fb90b11e
Ancestors: Collections-nice.826

Provide fastMultiply: helper #digitShiftSum:

=============== Diff against Collections-nice.826 ===============

Item was added:
+ ----- Method: Interval>>digitShiftSum: (in category 'enumerating') -----
+ digitShiftSum: aBlock
+ 	"Reconstruct an Integer that has been split in chunks by using shift and add.
+ 	Each of my element represent a digitShift, an my step size repreent the digit length of chunks.
+ 	The block is evaluated with each digitShift to produce the chunks.
+ 	
+ 	Algorithm insights:
+ 	Let d0,d1,d2,... be the chunks, and s be the bit shift (8*step because digitLength is 8bits)
+ 	The naive loop does shift each chunk and accumulate into a sum:
+ 		((d0 + (d1<<s)) + (d2<<s)) + (d3<<s) + ...
+ 	The length of accumulator increase at each iteration (1+2+3...) resulting in a cost (size+1)*size/2, or O(size^2)
+ 	Note that Horner scheme would be of about same cost
+ 		(((... + d3) << s + d2) << s + d1) << s + d0
+     	(a bit like so called Shlemiel the painter)
+ 	If we instead divide and conquer, we add smaller parts (1+1+2+...) resulting into a cost of O(size*log2(size))
+ 		(d0 + (d1<<s)) + ((d2 + (d3<<s)) << s) + ...
+ 	However, the divide and conquer split comes with an additionnal cost, so do it only if worth it."
+    
+     | sz half offset |
+ "Naive loop in O(size^2)/2 is best for small size"
+     (sz := self size) <= 8 ifTrue: [^self inject: 0 into: [:sum :shift | ((aBlock value: shift) bitShift: 8 * shift) + sum]].
+     half := sz // 2.
+     offset := half * step + start.
+     ^((start to: half - 1 * step + start by: step) digitShiftSum: aBlock)
+         + (((0 to: self last - offset by: step) digitShiftSum: [:k | aBlock value: offset + k]) bitShift: 8 * offset)!