Friday, November 13, 2009

The Array Multiplication Problem Solution

Use logarithms. They allow us multiply / divide numbers without using multiplication or division.

Find S = log(A[0]) + log(A[1]) + ... + log(A[N]). This takes O(n) time.
Set B[i] = antilog(S - log(A[i])) where i = 1:N. This also takes O(n) time.

B[i] = antilog(S - log(A[i]))
B[i] = antilog(log(A[0]) + log(A[1]) + ... + log(A[N]) - log(A[i]))
B[i] = antilog(log(A[0] * A[1] * ... * A[N] / A[i]))
B[i] = A[0] * A[1] * ... * A[N] / A[i]

No comments:

Post a Comment