CODEWITHSUNDEEP
dart
Allan
Allan

Reputation: 83

Math in Dart - working with numbers other than base 10

I was trying to do some math in something other than base 10, and wanted to get some input from the Dart community on possible directions I can take.

So, for example, suppose p = 2. Then, looking at 100 in base 2:

100 = (1 · 26
) + (1 · 25
) + (0 · 24
) + (0 · 23
) + (1 · 22
) + (0 · 21
) + (0 · 20
)

so

100 base 2 = 1100100

Add 1 to each digit and multiply the answers together:

(1 + 1)(1 + 1)(0 + 1)(0 + 1)(1 + 1)(0 + 1)(0 + 1) = 8

Try it for 3:

100 = (1 · 34
) + (0 · 33
) + (2 · 32
) + (0 · 31
) + (1 · 30
)

so

100 base 3 = 10201

(1 + 1)(0 + 1)(2 + 1)(0 + 1)(1 + 1) = 12

In Dart, I came up with the following;

https://gist.github.com/anonymous/11345381

int rows = 1000000000;
      int total = 0;
      for(int i = 0 ; i < rows ; i++ ){
        total += i.toRadixString(7)
            .split('')
            .map((s) => int.parse(s) + 1)
            .reduce((prev,next) => prev*next);
      }
print('${total} results');

This does work, and seems to be ok for small number of rows. But for larger numbers, it is really quite slow.

As shown, I am converting an int to a string (resulting in a string representation of a number), splitting it, mapping the split characters back to ints, adding 1 to each int, and then multiplying them all together.

Am I missing something when it comes to working with numbers in Dart, other than base 10?

Upvotes: 3

Views: 1183

Answers (1)

lrn
lrn

Reputation: 71803

Going through the string seems inefficient. How about doing it directly? 

int digitProduct(int n, int base) {  // non-negative n and base only
  int product = 1;
  while (n > 0) {
    int digit = n % base;
    n = n ~/ base;
    product *= (digit + 1);
  }
  return product;
}
main() {
  int rows = 1000000000;
  int total = 0;
  for (int i = 0; i < rows; i++) {
    total += digitProduct(i, 7);
  }
  print("${total} results");
}

Also 1000000000 is a pretty big number. If it takes a microsecond per row, it will still take ~16 minutes to complete.

Division by arbitrary bases is slow. If you hardcode the base to be 7, it'll probably be significantly faster (I expect ~90% of the time spent in digitProduct to be used on ~/ and %).

Upvotes: 2

Related Questions