0
$\begingroup$

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)?

$\endgroup$
  • 2
    $\begingroup$ Where does the modular multiplication come in ? Otherwise, use logarithms. $\endgroup$ – Joffan Jun 8 '16 at 20:48
  • $\begingroup$ By "first digit", do you mean first from the left or first from the right, i.e. most significant or least significant? $\endgroup$ – Robert Israel Jun 8 '16 at 20:53
  • 2
    $\begingroup$ Possible duplicate of First digit of a very long number $\endgroup$ – TonyK Jun 8 '16 at 22:44
  • $\begingroup$ This is exactly what logarithms are great for—keeping track of the most significant digits of a product. $\endgroup$ – Greg Martin Jun 8 '16 at 22:53
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ no not the units digit, i want the left most digit $\endgroup$ – Sayan Ghosh Jun 8 '16 at 21:20
  • $\begingroup$ 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. $\endgroup$ – Nij Jun 8 '16 at 21:28
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.