4
$\begingroup$

Beside *10^n, is there a faster way to add thousands of zeros to end of a number?

Updated

Timings:

In[230]:= First[Timing[prime*10^100000000]]

Out[230]= 3.625

In[25]:= First[
 Timing[FromDigits[
   Join[IntegerDigits[prime], ConstantArray[0, 100000000]]]]]

Out[25]= 7.547

Updated

According to Mr.Wizard answer:

In[46]:= First[Timing[2213*1*^200000000]]

Out[46]= 0.015 (* The real timing on the clock is 5 seconds *)

In[45]:= First[Timing[2213*10^200000000]]

Out[45]= 5.11

In[3]:= First[Timing[ToExpression["2213*1*^200000000"]]]

Out[3]= 5.078

But the strange thing is that by using special 1*^ notation, the reported timing is almost zero while by clock it takes roughly the same time of 10^n. Maybe Timing function doesn't take Mathematica built-in notations into account.!!

Updated 2

Yet The fastest method to beat native *^10 adding zero method is by shifting, even though the improvement is very tiny.

In[16]:= First[Timing[1223*10^100000000]]

Out[16]= 2.625

In[17]:= First[Timing[BitShiftLeft[1223*5^100000000, 100000000]]]

Out[17]= 2.547
$\endgroup$
7
  • $\begingroup$ Can you provide the problem example where performance suffers from slow expanding of number by zeroes at its end? $\endgroup$ Nov 24, 2012 at 12:35
  • $\begingroup$ In the Karatsuba multiplication where number = A*10^n + B and numbernumber = AA*10^2n + 2AB*10^n + BB. n can be very large. $\endgroup$ Nov 24, 2012 at 13:02
  • 2
    $\begingroup$ I think there is no way to improve this thing in Mathematica: 1) obviously, translation to/from list representation of integers makes your code slower. 2) using Compile also will give no effect because you use very big numbers those cannot be fitted by machine numbers. Mathematica is well suited for symbolic computations and prototyping of numerical algorithms but not for great numerical performance. $\endgroup$ Nov 24, 2012 at 13:51
  • $\begingroup$ @Piotr Semenov What improved speeds can you obtain, in any other language, when multiplying numbers in the 10^8 digit size range? $\endgroup$ Nov 24, 2012 at 21:31
  • $\begingroup$ @Daniel Lichtblau I mean the absolute time that program takes to run. For example, I am not ok with 1.5 hours that Mathematica spends doing some stuff. So in this case I prefer writing fast C++ code that takes several seconds of time to do the same stuff. So I claimed that you have to choose more suitable environment to have great performance. Mathematica's usage is limited for applications those are to be as fast as possible. $\endgroup$ Nov 25, 2012 at 11:04

2 Answers 2

8
$\begingroup$

My original answer is incorrect -- it is preserved as a record of my own hubris. :^)

Simply, as Rojo points out, the calculation is still being done with 1*^1000, it's just being done at a different time. One may see this by manually observing the time taken for evaluation on an idle machine, or by setting this option which will print the total time taken to evaluate a Cell of code:

SetOptions[$FrontEnd, EvaluationCompletionAction -> "ShowTiming"]

The syntax n*^x is still useful when making definitions as it evaluates before the definition is made. For example, a function defined f1 = # * 1*^100000000 & will be faster in use than f2 = # * 10^100000000 & because the huge coefficient is only calculated once, but it is still calculated.

Logically, since Mathematica still runs on a binary system, a mantissa of two does not have the overhead that a decimal one has:

1*^100000000;
(* Time: 2.18 seconds *)

2^332200000;
(* Time: 0.00 seconds *)

There is a simple solution to this problem and it relies on a specific input form (*^):

prime = Prime @ 813580;

First[Timing[prime*10^100000000]]

First[Timing[prime*1*^100000000]]

2.106

0.

Crucially, 1*^1000 is directly interpreted by Mathematica as the number 101000 while 10^1000 actually calculates this number.


This turns out to be anything but "simple" as I cannot think of a clean way to insert exponents programmatically into the input syntax n*^exp in a manner than retains its benefit.

Hardly nice, but at least as a proof of concept one could bodge this together with $PreRead:

$PreRead = # /. 
    RowBox[{"zeros", "[", exp_, "]"}] :> 
     "1*^" <> ToString@ToExpression@exp &;

prime = Prime @ 813580;
e = 100000000;

prime*zeros[e]; // AbsoluteTiming // First

0.0110006

prime*zeros[e] === prime*1*^100000000

True

$\endgroup$
16
  • 1
    $\begingroup$ Your solution does the magic but how can I use it with variables like First[AbsoluteTiming[prime*1*^ e]]. It gives error $\endgroup$ Nov 24, 2012 at 14:15
  • 3
    $\begingroup$ thanks for your reply but using ToExpression causes Mathametica to calculate the result again. Timing become 2.453 again $\endgroup$ Nov 24, 2012 at 14:24
  • 1
    $\begingroup$ @MohsenAfshin I'm not surprised; it is a very limited replacement rule as written. You'll also not be able to use zeros @ x or x // zeros. As I said this will need to be made more robust if it is to actually be used. I'm still bothered that I can't find a better way so I keep looking, rather than improving this, but if I come up empty in a day or two I'll rewrite this to be at least passably practical. $\endgroup$
    – Mr.Wizard
    Nov 24, 2012 at 23:21
  • 3
    $\begingroup$ I think the problem is that 1*^200000 also has to "do the calculation". It't just that it's done in the parsing stage before any timing function can get to report it. So, there's nothing advantagous in principle about trying to do the math while parsing, and as soon as you move the parsing inside a timing function (by using ToExpression) you get a reality report $\endgroup$
    – Rojo
    Nov 25, 2012 at 20:24
  • 1
    $\begingroup$ @Rojo FACEPALM -- Oh dear, I'm afraid you're right. Talk about embarrassing, but as always I learn from these things. Now, what do I do with this post? $\endgroup$
    – Mr.Wizard
    Nov 25, 2012 at 23:54
0
$\begingroup$

You could try timing this method:

FromDigits[Join[{123}, ConstantArray[0, 20]]]

12 300 000 000 000 000 000 000

$\endgroup$
3
  • 1
    $\begingroup$ IntegerDigits[123] is an extra that can be easily removed. One can perform just by FromDigits[{123}~Join~ConstantArray[0,20]]. But I think this code is slower than just 123 * 10^n due to translation to/from list representation of integer. $\endgroup$ Nov 24, 2012 at 13:38
  • $\begingroup$ It doubles processing time $\endgroup$ Nov 24, 2012 at 13:40
  • $\begingroup$ The time consuming phase is FromDigits not the joining phase. $\endgroup$ Nov 24, 2012 at 13:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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