0

Let there be many numbers $a_1,a_2,a_3,\dots,a_n$.

I want to find the first digit of their product, i.e. of $A=a_1\times a_2\times a_3\times a_4\times \dots\times a_n$.

These numbers are huge and multiplying all of them exceeds the time limit.

Is there any shortcut to find the most significant digit of $A$ (first digit from the left)?

Nij
  • 2,991
Sayan Ghosh
  • 99

3 Answers3

1

If "first digit" refers to the digit of units, then you can work modulo $10$.
Simply multiply the digit of units of two of the numbers, and then take the digit of units from the result. Multiply it by the digit of units of the next number, and take the digit of units there.
Continue until you have computed all products, then the digit of units is the answer required.
In particular, note that any $0$ makes the answer also $0$, as will any combination of a $5$ with an even digit of units. Any $1$s can be ignored as they don't change the result of multiplication.

Nij
  • 2,991
  • no not the units digit, i want the left most digit – Sayan Ghosh Jun 08 '16 at 21:20
  • Then no, there is no shortcut. With enough numbers and absent some very particular conditions on all of their digits, you need to perform the whole multiplication to be accurate. Even using significant digits quickly becomes unhelpful. – Nij Jun 08 '16 at 21:28
1

You can multiply the leading three or four digits (depending on $n$). It is not guaranteed, as your result could come out $799xxx$ and the trailing digits you have ignored could push you over $8$ for a leading digit. With some extra work, you can prove that there is no carry. Say you have decided to use the leading four digits and one of your $a$'s is $123,456,789$. You could say it is between $123,400,000$ and $123,500,000$. Do this for all the $a$'s, then multiply the minima and the maxima. If they agree on the leading digit, you are done. If not, you need to carry more digits. As long as you are not unlucky enough to come very close to a carry, it will work out.

Ross Millikan
  • 374,822
1

Might not be a mathematically brilliant way to solve your problem, but adding logs is always computationally faster than multiplying numbers, and it sounds like you are using a computer to get some big number.

Have you tried:

$ln(A)= ln(a_1) + ln(a_2) + ln(a_3) + ln(a_4) \dots + ln(a_n)$.

$A= e^{ ln(a_1) + ln(a_2) + ln(a_3) + ln(a_4) \dots + ln(a_n) }$.

I am assumeing your values are real, and then don't have to worry about riemann sheets \ branch cuts.

D A
  • 199