# Optimizing Multiplication Table

I have a class that takes an array of integers and produces a multiplication table.

class MultiplicationTable
def initialize(num_ary)
@num_ary = num_ary.to_a
end

def generate
a1 = @num_ary.clone
a2 = @num_ary.clone

rows = []
rows << a1

a2.shift

a2.each do |x|
cols = [x]
a1[1..-1].each do |y|
cols << (x * y)
end
rows << cols
end

rows
end
end


So this:

MultiplicationTable.new(1.upto(5)).generate


produces this output:

[
[1, 2, 3, 4, 5],
[2, 4, 6, 8, 10],
[3, 6, 9, 12, 15],
[4, 8, 12, 16, 20],
[5, 10, 15, 20, 25]
]


Here are my results from benchmarking:

                         user     system      total        real
100 entry table      0.000000   0.000000   0.000000 (  0.001295)
1,000 entry table    0.120000   0.010000   0.130000 (  0.132325)
10,000 entry table  15.290000   0.380000  15.670000 ( 15.747799)


Is there anything I can do to speedup/improve up this code?

You only need to compute half the table because it is symmetrical; for your line

a1[1..-1].each do |y|


a1[x..-1].each do |y|


and if you ever need to look up a * b where b > a, instead look up b * a

This will create a multiplication table that looks like this:

# old table
1  2  3  4  5
1 1  2  3  4  5
2 2  4  6  8 10
3 3  6  9 12 15
4 4  8 12 16 20
5 5 10 15 20 25

# new table
1 2 3  4  5
1 1 2 3  4  5
2   4 6  8 10
3     9 12 15
4       16 20
5          25

# final multiplication table
arr = [
[1,2,3,4,5],
[4,6,8,10],
[9,12,15],
[16,20],
[25]
]


To access a*b where a >= b, the answer is in arr[a-1][b-a]
To access 3*4, the answer is in row 3-1, element 4-3 = arr[3-1][4-3] = arr[2][1] = 12
To access 5*2 (= 2*5), the answer is in row 2-1, element 5-2 = arr[2-1][5-2] = arr[1][3] = 10
To access 100x100 (assuming the range goes high enough), arr[99][0]

You'll need to do something slightly different if you are passing an array that isn't 1..x - in that case, first look up the index of each of the two numbers in the original array and use THEM in the arr[a-1][b-a] lookup. I suspect you'll need to subtract 1 from the indices but I haven't worked it out in my head.

The code is a lot more complicated than it needs to be. This produces the same result with approximately the same performance:

def multiplication_table(size)
(1..size).collect { |x| (1..size).collect { |y| x * y } }
end

multiplication_table(10000)


As a general rule, most code that appends elements to an empty array in a loop can be simplified using Enumerable#collect.