Математическая навигация по большой двумерной числовой сетке в C#

Я пытаюсь найти определенные координаты интереса в очень большой виртуальной сетке. Эта сетка на самом деле не существует в памяти, поскольку размеры огромны. Ради этого вопроса, давайте предположим, что эти измерения (Width x Height) = (Int32.MaxValue x Int32.MaxValue),

  1   2   3   4   5   6   7   8   9  10
  2   4   6   8  10  12  14  16  18  20
  3   6   9  12  15  18  21  24  27  30
  4   8  12  16  20  24  28  32  36  40
  5  10  15  20  25  30  35  40  45  50
  6  12  18  24  30  36  42  48  54  60
  7  14  21  28  35  42  49  56  63  70
  8  16  24  32  40  48  56  64  72  80
  9  18  27  36  45  54  63  72  81  90
 10  20  30  40  50  60  70  80  90 100

Известные данные о сетке:

  • Размеры сетки = (Int32.MaxValue x Int32.MaxValue),
  • Значение в любой данный момент (x, y) координата = произведение X и Y = (x * y),

Учитывая приведенный выше большой набор конечных чисел, мне нужно вычислить набор координат, значение которых (x * y) это сила e, Скажем e 2 в этом случае.

Поскольку цикл по сетке не вариант, я подумал о циклическом прохождении:

int n = 0;
long r = 0;
List<long> powers = new List<long>();
while (r < (Int32.MaxValue * Int32.MaxValue))
{
    r = Math.Pow(e, n++);
    powers.Add(r);
}

Это дает нам уникальный набор полномочий. Теперь мне нужно выяснить, по каким координатам существует каждая сила. Давайте принимать 2^3=8, Как показано в таблице выше, 8 существует в 4 координатах: (8,1), (4,2), (2,4) & (1, 8),

Очевидно, что проблема здесь заключается в нахождении нескольких факторов числа 8, но это стало бы непрактичным для больших чисел. Есть ли другой способ добиться этого, и я что-то упустил?

  • Использование наборов не будет работать, так как факторы не существуют в памяти.
  • Есть ли творческий способ учитывать, зная, что рассматриваемое число всегда будет силой e?
Источник

2 ответа

Решение

Другое решение, не такое сложное, как идея Commodore63, но, следовательно, может быть немного проще (не нужно выполнять простую факторизацию и вычислять все правильные подмножества):

const int MaxX = 50;
const int MaxY = 50;
const int b = 6;

var maxExponent = (int)Math.Log((long)MaxX * MaxY, b);

var result = new List<Tuple<int, int>>[maxExponent + 1];
for (var i = 0; i < result.Length; ++i)
  result[i] = new List<Tuple<int, int>>();

// Add the trivial case
result[0].Add(Tuple.Create(1, 1));

// Add all (x,y) with x*y = b
for (var factor = 1; factor <= (int)Math.Sqrt(b); ++factor)
  if (b % factor == 0)
    result[1].Add(Tuple.Create(factor, b / factor));

// Now handle the rest, meaning x > b, y <= x, x != 1, y != 1
for (var x = b; x <= MaxX; ++x) {
  if (x % b != 0)
    continue;

  // Get the max exponent for b in x and the remaining factor
  int exp = 1;
  int lastFactor = x / b;
  while (lastFactor >= b && lastFactor % b == 0) {
    ++exp;
    lastFactor = lastFactor / b;
  }

  if (lastFactor > 1) {
    // Find 1 < y < b with x*y yielding a power of b
    for (var y = 2; y < b; ++y)
      if (lastFactor * y == b)
        result[exp + 1].Add(Tuple.Create(x, y));
  } else {
    // lastFactor == 1 meaning that x is a power of b
    // that means that y has to be a power of b (with y <= x)
    for (var k = 1; k <= exp; ++k)
      result[exp + k].Add(Tuple.Create(x, (int)Math.Pow(b, k)));
  }
}

// Output the result
for (var i = 0; i < result.Length; ++i) {
  Console.WriteLine("Exponent {0} - Power {1}:", i, Math.Pow(b, i));
  foreach (var pair in result[i]) {
    Console.WriteLine("  {0}", pair);
    //if (pair.Item1 != pair.Item2)
    //  Console.WriteLine("  ({0}, {1})", pair.Item2, pair.Item1);
  }
}
Источник

Лучший способ состоит в том, чтобы включить в него простые компоненты. Допустим, они следующие: {a^m, b^p, c^q}. Затем вы строите множество для каждой степени e, например, если m = 2, p = 1, q = 3,

e ^ 1 = {a, a, b, c, c, c}

e ^2 = (a, a, a, a, b, b, c, c, c, c, c, c}

и т. д. до e^K > Int32.MaxValue * Int32.MaxValue

затем для каждого набора необходимо выполнить итерацию по каждому уникальному подмножеству этих наборов, чтобы сформировать одну координату. Другая координата - это то, что остается. Вам понадобится один вложенный цикл для каждого из уникальных простых чисел в e. Например:

Скажем за е ^2

  M=m*m;
  P=p*p;
  Q=q*q;

  c1 = 1 ;
  for (i=0 ; i<=M ; i++)
  {
    t1 = c1 ;
    for (j=0 ; j<=P ; j++)
    {
      t2 = c1 ;
      for (k=0 ; k<=Q ; k++)
      {
        // c1 holds first coordinate
        c2 = e*e/c1 ;
        // store c1, c2

        c1 *= c ;
      }
      c1 = t2*b ;
    }
    c1 = t1*a ;
  }

Должно быть (M+1)(P+1)(Q+1) уникальных координат.

Источник
Другие вопросы по тегам