c# - How to calculate the digit products of the consecutive numbers efficiently? -

i'm trying calculate product of digits of each number of sequence of numbers, example:

21, 22, 23 ... 98, 99 ..

would be:

2, 4, 6 ... 72, 81 ..

to reduce complexity, consider [consecutive numbers] in limited length of digits, such 001 999 or 0001 9999.

however, when sequence large, example, 1000000000, repeatedly extract digits , multiply every number inefficient.

the basic idea skip consecutive zeros encounter during calculation, like:

using system.collections.generic; using system.linq; using system;  // note digit product not given iteration // need provide delegate calculation public static partial class numericextensions {     public static void numberiteration(             int value, action<int, int[]> delg, int radix=10) {         var digits=digititerator(value, radix).toarray();         var last=digits.length-1;         var emptyarray=new int[] { };         var pow=(func<int, int, int>)((x, y) => (int)math.pow(x, 1+y));         var weights=enumerable.repeat(radix, last-1).select(pow).toarray();          for(int complement=radix-1, i=value, j=i; i>0; i-=1)             if(i>j)                 delg(i, emptyarray);             else if(0==digits[0]) {                 delg(i, emptyarray);                  var k=0;                  for(; k<last&&0==digits[k]; k+=1)                     ;                  var y=(digits[k]-=1);                  if(last==k||0!=y) {                     if(0==y) { // implied last==k                         digits=new int[last];                         last-=1;                     }                      for(; k-->0; digits[k]=complement)                         ;                 }                 else {                     j=i-weights[k-1];                 }             }             else {                 // receives digits of number doesn't contain zeros                  delg(i, digits);                  digits[0]-=1;             }          delg(0, emptyarray);     }      static ienumerable<int> digititerator(int value, int radix) {         if(-2<radix&&radix<2)             radix=radix<0?-2:2;          for(int remainder; 0!=value; ) {             value=math.divrem(value, radix, out remainder);             yield return remainder;         }     } } 

this enumeration of numbers, avoid numbers contain zeros calculated in first place, digit products not yet given code; generate digit products providing delegate perform calculation still take time.

how calculate digit products of consecutive numbers efficiently?

edit: "start anywhere, extended range" version...

this version has signficantly extended range, , therefore returns ienumerable<long> instead of ienumerable<int> - multiply enough digits , exceed int.maxvalue. goes 10,000,000,000,000,000 - not quite full range of long, pretty big :) can start anywhere like, , carry on there end.

class digitproducts {     private static readonly int[] prefilled = createfirst10000();      private static int[] createfirst10000()     {         // inefficient simple, , executed once.         int[] values = new int[10000];         (int = 0; < 10000; i++)         {             int product = 1;             foreach (var digit in i.tostring())             {                 product *= digit -'0';             }             values[i] = product;         }         return values;     }      public static ienumerable<long> getproducts(long startingpoint)     {         if (startingpoint >= 10000000000000000l || startingpoint < 0)         {             throw new argumentoutofrangeexception();         }         int = (int) (startingpoint / 1000000000000l);         int b = (int) ((startingpoint % 1000000000000l) / 100000000);         int c = (int) ((startingpoint % 100000000) / 10000);         int d = (int) (startingpoint % 10000);          (; < 10000; a++)         {             long amultiplier = == 0 ? 1 : prefilled[a];             (; b < 10000; b++)             {                 long bmultiplier = == 0 && b == 0 ? 1                                  : != 0 && b < 1000 ? 0                                  : prefilled[b];                 (; c < 10000; c++)                 {                     long cmultiplier = == 0 && b == 0 && c == 0 ? 1                                      : (a != 0 || b != 0) && c < 1000 ? 0                                      : prefilled[c];                      long abcmultiplier = amultiplier * bmultiplier * cmultiplier;                     (; d < 10000; d++)                     {                         long dmultiplier =                              (a != 0 || b != 0 || c != 0) && d < 1000 ? 0                             : prefilled[d];                         yield return abcmultiplier * dmultiplier;                     }                     d = 0;                 }                 c = 0;             }             b = 0;         }     } } 

---

edit: performance analysis

i haven't looked @ performance in detail, believe @ point bulk of work iterating on billion values. simple for loop returns value takes on 5 seconds on laptop, , iterating on digit products takes bit on 6 seconds, don't think there's more room optimization - if want go start. if want (efficiently) start different position, more tweaks required.

---

okay, here's attempt uses iterator block yield results, , precomputes first thousand results make things bit quicker.

i've tested 150 million, , it's correct far. goes returns first billion results - if needed more that, add block @ end...

static ienumerable<int> getproductdigitsfast() {     // first generate first 1000 values cache them.     int[] productperthousand = new int[1000];      // 9     (int x = 0; x < 10; x++)     {         productperthousand[x] = x;         yield return x;     }     // 99     (int y = 1; y < 10; y++)     {         (int x = 0; x < 10; x++)         {             productperthousand[y * 10 + x] = x * y;             yield return x * y;         }     }     // 999     (int x = 1; x < 10; x++)     {         (int y = 0; y < 10; y++)         {             (int z = 0; z < 10; z++)             {                 int result = x * y * z;                 productperthousand[x * 100 + y * 10 + z] = x * y * z;                 yield return result;             }         }     }      // use cached values rest     (int x = 0; x < 1000; x++)     {         int xmultiplier = x == 0 ? 1 : productperthousand[x];         (int y = 0; y < 1000; y++)         {             // we've yielded first thousand             if (x == 0 && y == 0)             {                 continue;             }             // if x non-zero , y less 100, we've             // got 0, result 0. otherwise,             // use productperthousand.             int ymultiplier = x == 0 || y >= 100 ? productperthousand[y]                                                  : 0;             int xy = xmultiplier * ymultiplier;             (int z = 0; z < 1000; z++)             {                 if (z < 100)                 {                     yield return 0;                 }                 else                 {                     yield return xy * productperthousand[z];                 }             }         }     } } 

i've tested comparing results of incredibly naive version:

static ienumerable<int> getproductdigitsslow() {     (int = 0; < 1000000000; i++)     {         int product = 1;         foreach (var digit in i.tostring())         {             product *= digit -'0';         }         yield return product;     } } 

hope idea of use... don't know how compares others shown here in terms of performance.

edit: expanding slightly, use simple loops know results 0, end fewer conditions worry about, reason it's slower. (this surprised me.) code longer, possibly little easier follow.

static ienumerable<int> getproductdigitsfast() {     // first generate first 1000 values cache them.     int[] productperthousand = new int[1000];      // 9     (int x = 0; x < 10; x++)     {         productperthousand[x] = x;         yield return x;     }     // 99     (int y = 1; y < 10; y++)     {         (int x = 0; x < 10; x++)         {             productperthousand[y * 10 + x] = x * y;             yield return x * y;         }     }     // 999     (int x = 1; x < 10; x++)     {         (int y = 0; y < 10; y++)         {             (int z = 0; z < 10; z++)             {                 int result = x * y * z;                 productperthousand[x * 100 + y * 10 + z] = x * y * z;                 yield return result;             }         }     }      // use cached values 999,999     (int x = 1; x < 1000; x++)     {         int xmultiplier = productperthousand[x];         (int y = 0; y < 100; y++)         {             yield return 0;         }         (int y = 100; y < 1000; y++)         {             yield return xmultiplier * y;         }     }      // use cached values rest     (int x = 1; x < 1000; x++)     {         int xmultiplier = productperthousand[x];         // within each billion, first 100,000 values have         // second digit of 0, can yield 0.         (int y = 0; y < 100 * 1000; y++)         {             yield return 0;         }         (int y = 100; y < 1000; y++)         {             int ymultiplier = productperthousand[y];             int xy = xmultiplier * ymultiplier;             // within each thousand, first 100 values have             // anti-penulimate digit of 0, can yield 0.             (int z = 0; z < 100; z++)             {                 yield return 0;             }             (int z = 100; z < 1000; z++)             {                 yield return xy * productperthousand[z];             }         }     } }