Provide an algorithm to multiply a series of Base 3 integers, represented as strings, without converting to any other base during any part of the algorithm. Each string (Base 3 integer) may have an arbitrary number of digits.
You may not use arithmetic operations on the digits in a way that is equivalent to changing the base, although you may use a dictionary or table lookup to recognize, for example, that in Base 3, 2*2 = 11.
You can use any programming language, or pseudo-code, or provide a verbal description.
I'm on the fence over whether this approach truly doesn't perform any operation that could be construed as changing the base, but I'll share it anyway because I thought it was an interesting problem. I've used ruby here since that's what was handy, but I think the sense of it is clear enough if that's not one of your languages.
usage: BaseMultiplier.multiply '102', '201', '11', '221'
example: BaseMultiplier.multiply '212', '1022', '10' = 10022110
Bonus -- see the same multiplication interpreted in another base by overriding the default of '3' [DOES NOT WORK WITH BASES > 10]
example: BaseMultiplier.multply '212', '1022', '10', base: 10 = 2166640
I've made no attempt to handle weirdness in the input like non-digit characters or digits inconsistent with the base like 'foo' or '13' but a robust implementation would certainly include that handling.
class BaseMultiplier
def self.multiply(*items, base: 3)
return items[0] if items.count == 1 # one item means nothing to multiple
return multiply_pair(items[0], items[1], base:) if items.count == 2 # no need for recursion
elem = items.shift
multiply_pair(elem, multiply(*items, base:), base:) # multiply the first by the product of the rest
end
def self.multiply_pair(a, b, base: 3)
adig = a.split('').map(&:to_i).reverse # digits, converted to numbers with least significant first
bdig = b.split('').map(&:to_i).reverse
buckets = Hash.new(0) # will store digit products grouped by place
# multiply each pair of digits, and offset the result by the total number of "places"
adig.each_with_index do |dig1, dig1_index|
bdig.each_with_index do |dig2, dig2_index|
bucket = dig1_index + dig2_index
buckets[bucket] += dig1 * dig2
end
end
# now handle carrying to ensure no digit exceeds the base
buckets.keys.sort.each do |k| # sort ensures we work from least significant to most
if (val = buckets[k]) >= base
buckets[k] = val % base
buckets[k+1] += (val - (val % base)) / base
end
end
# collect the digits, and reverse since the first is the least significant
buckets.keys.sort.reverse.map{|k| buckets[k]}.join('')
end
end
|
|
Posted by Paul
on 2023-03-27 14:04:19 |
Possible solution
