Group Abstract Group Abstract

Message Boards Message Boards

Compile to find digits ratio of integers composed by sequential numbers?

Hello community, I'm trying to optimize the speed of a code using Parallelize and Compile but I'm not having very expressive results (I'm still inexperienced in these commands). I believe that I am using these commands in an inefficient way (my attempt is at the end of the post)... below is explained where is the problem for my case in detail. First I'll explain the context of my question and then explain what I want to do.

Taking the table of the following numbers for example:

z = 5;
FromDigits[Table[10^x - 1, {x, {Range[z]}}]]

ima1

I then transformed into integers composed of sequential numbers as follows:

z = 2;
FromDigits[Table[10^x - 1, {x, {Range[z]}}]]
g[k_] := (ToExpression[
    StringDelete[
     ToString[Table[i, {i, Range[k]}]], {"{", "}", " ", ","}]]);
Table[g[j1], {j1, FromDigits[Table[10^x - 1, {x, {Range[z]}}]]}]

ima2

To count the different digits of each of these numbers:

z = 6;
g[k_] := (DigitCount[
    ToExpression[
     StringDelete[
      ToString[Table[i, {i, Range[k]}]], {"{", "}", " ", ","}]]]);
Table[Print[g[j1]], {j1, 
  FromDigits[Table[10^x - 1, {x, {Range[z]}}]]}]

ima3

And finally, make a relationship (ratio) between the number of digits ´0´ (which is less than any other digit) and another digit (e.g. ´2´):

z = 6;
g[j_, h_] := (Take[
    DigitCount[
     ToExpression[
      StringDelete[
       ToString[Table[i, {i, 1, j}]], {"{", "}", " ", ","}]]], {h}]);
Table[g[k1, 10], {k1, FromDigits[Table[10^x - 1, {x, {Range[z]}}]]}]
Table[g[k2, 2], {k2, FromDigits[Table[10^x - 1, {x, {Range[z]}}]]}]
Table[g[k3, 10]/g[k3, 2], {k3, 
  FromDigits[Table[10^x - 1, {x, {Range[z]}}]]}]
Table[N[g[k4, 10]/g[k4, 2], 11], {k4, 
  FromDigits[Table[10^x - 1, {x, {Range[z]}}]]}]

ima4

The largest number of terms I can calculate is 8 before it crashes (?!) the program. Below the result obtained for 8 terms without using Parallelize or Compile:

EvaluationData[z = 8;
 a = FromDigits[Table[10^x - 1, {x, {Range[z]}}]];
 g[j_, h_] := (Take[
    DigitCount[
     ToExpression[
      StringDelete[
       ToString[Table[i, {i, 1, j}]], {"{", "}", " ", ","}]]], {h}]);
 b = Flatten[Table[N[g[k4, 10]/g[k4, 2], 11], {k4, a}]];
 {ListLinePlot[b, 
   PlotRange -> {{1, Automatic}, {Automatic, Automatic}}, 
   LabelingFunction -> (#1 &), ImageSize -> Large], b}]

ima5

Using the result data I can make an estimate of the equation governing these fractions based on experimental (result made only by observing the first 8 terms; by guessing) and also test the value of the guessed equation at the infinite limit:

u: {1,2,3,4,5,6,7,8}

num = numerator: {0,9,189,2889,38889,488889,5888889,68888889}

dem = denominator: {1,20,300,4000,50000,600000,7000000,80000000}

z = 8;
num = (10 - 10^(1 + u) + 9*u*10^u)/90
dem = u*10^(u - 1)
sim = Simplify[num/dem]
Table[N[(-10 + 10^(1 - u) + 9*u)/(9*u), 11], {u, Range[z]}]

Limit[sim, u -> \[Infinity]]

ima6

  • My attempt using Compile and Parallelize:

Now comes my attempt to improve the initial code using Parallelize and Compile to get the dots (experimental) with a better timing. I would like to be able to calculate faster and more points using the experimental code to check the data in the guessed equation. But I did not get a much better result due to my lack of experience using these commands...my attempt:

z = 8;
g = Compile[{{x, _Integer}}, Range[10^x - 1]]
EvaluationData[
 Parallelize[
  h[x1_] := (DigitCount[
     ToExpression[
      StringDelete[ToString[g[x1]], {"{", "}", " ", ","}]]])];
 b = Flatten[
   Table[N[Take[h[i], {10}]/Take[h[i], {2}], 11], {i, Range[z]}]];
 {ListLinePlot[b, 
   PlotRange -> {{1, Automatic}, {Automatic, Automatic}}, 
   LabelingFunction -> (#1 &), ImageSize -> Large], b}]

ima7

  • My question:

There was no significant improvement in computing time (approx. 10%) and I believe that discrete improvement was due to Parallelize and not to Compile. How do I use these commands to optimize this code and make it faster (or lighter..?)?? For I believe I did not know how to use them properly in the best way....

Thanks.

POSTED BY: Claudio Chaib
6 Replies

Hello, I managed to improve the time to find the sum of the digits of each type in this sequence of numbersÂ… My new result was 1/24 of the time of my best previous result (!), but I would like to know if anyone knows a method that makes it even better..? ... I would like a method that could sum the digits without creating an effective table ( because when a table is generated, the entire table is stored in memory, the best way would be something like While?! ), so that instead of creating a table the code would successively summing the digits "forgetting" the previous results for better performance... Please, if anyone knows a way to increase the sum of digits function in a more efficient way can you help me?

My new result:

f1[z_] := 
 Module[{k, x}, 
  N[Table[Last@
      Accumulate@
       ParallelTable[Count[IntegerDigits[x], 0], {x, 1, 10^k - 1}]/
     Last@Accumulate@
       ParallelTable[
        Count[IntegerDigits[x], 2], {x, 1, 10^k - 1}], {k, Range[z]}],
    11]]
ListLinePlot[f1[7], 
  PlotRange -> {{1, Automatic}, {Automatic, Automatic}}, 
  LabelingFunction -> (#1 &), ImageSize -> Large] // AbsoluteTiming

imag1

Thanks.

POSTED BY: Claudio Chaib

Could change Last@Accumulate@ParallelTable to Sum and that should keep memory consumption down.

POSTED BY: Daniel Lichtblau

Thank you very much Daniel... I was complicating the way to do it, but you reminded me that the simplest way is even better! I just switched Sum by ParallelSum and the result was: 1.045 seconds (66% of the previous time) and the memory improved even more..!

f1[z_] := 
 Module[{k, x}, 
  N[Table[ParallelSum[Count[IntegerDigits[x], 0], {x, 1, 10^k - 1}]/
     ParallelSum[Count[IntegerDigits[x], 2], {x, 1, 10^k - 1}], {k, 
     Range[z]}], 11]]
ListLinePlot[f1[7], 
  PlotRange -> {{1, Automatic}, {Automatic, Automatic}}, 
  LabelingFunction -> (#1 &), ImageSize -> Large] // AbsoluteTiming

Thanks.

POSTED BY: Claudio Chaib
POSTED BY: Claudio Chaib

Compile will only work with machine integers at this time. If ever it gets extended to work with bignums, the issue might stll be that the library code is bogged down handling large numbers. But it seems like excess to create these huge values to begin with. Could instead just iterate to 10^k-1 for whatever k, incrementing counts for each digit's appearances as you go. That is to say, when you encounter 32141, say, each counter for 2,3,4 gets increased by 1, and the counter for 1 gets increased by 2.

POSTED BY: Daniel Lichtblau

Thanks for the reply Daniel, I think I understand what you're telling me... Instead of counting the digits of the whole number I can count each part before joining, since the total sum of the digits are significantly smaller numbers... I will try to advance the count in the equation to a more initial position in it without having to create large numbers.

POSTED BY: Claudio Chaib
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard