Лучший способ хранения больших базовых номеров B?

Question

Каков наилучший способ хранения больших базовых чисел B, чтобы операции, такие как сдвиг вправо и проверка наименее значимого бита, могли быть выполнены эффективно?

На самом деле, я наткнулся на интервью вопрос, который говорит, что

Given two numbers N and K such that 0<=N<=1000 and 0<=K<=1000^1000. I need 
to check that whether N^N = K or not. For example: 

if N=2 and K=4 , 2^2 = 4 so return true; 
if N=3 and K=26 , 3^3 != 26 so return false 

То, что я думал, что если я считаю base N number system, то N^N будет эквивалентно 1 followed by N zero в нем. Например, для N = 2, 2^2 = 100 (в базе 2), для N = 3, 3^3 = 1000 (в базе 3). Затем я могу легко написать функцию, чтобы определить, есть ли K = N^N или нет.

int check(unsigned long int N, unsigned long int K) 
{ 
    unsigned long int i; 
    for (i=0; i<N; i++) 
    { 
     if (K%N != 0) //checking whether LSB is 0 or not in base N number system 
      return 0; 
     K = K/N; //right shift K by one. 
    } 
    return (K==1); 
} 

В настоящее время существует две основные проблемы, связанные с этой функцией:

1) An unsigned long int is not sufficient to store large numbers of range 0 
to 1000^1000. 
2) The modulus and the division operations makes it every less efficient. 

Для того, чтобы сделать его эффективным, Ищу какой-то способ для представления большой базы N чисел, так что я могу выполнить сдвиг вправо и эффективно проверять операции с наименее значимыми бит. Кто-нибудь раньше сталкивался с этим? Или кто-нибудь знает какой-либо другой способ эффективно решить эту проблему?

Answer 1

Почему вы хотите преобразовать числа в базу N?

Вы можете продолжать делиться на N. Если вы получаете 1 после N таких делений, то это N^N. иначе это не так.

Вам нужно будет хранить K как строку и выполнить операцию деления.

divide(k,n): 
    c = '' 
    a = '' 
    for i in k: 
    c = c+i 
    a = a+ str(int(c)/ int(n)) 
    c = str(int(c) % int(n)) 
return a 

это в Python, вы можете реализовать что-то подобное в C

Answer 2

Для проверки равенства вы на самом деле не нужно делать высокую точность арифметика - вы можете использовать http://en.wikipedia.org/wiki/Chinese_remainder_theorem. Найдите достаточно простых чисел, чтобы гарантировать, что их произведение больше N^N, а затем проверяет N^N на K по модулю каждого из простых чисел по очереди.

На практике я, вероятно, использовал бы пакет Java BigInteger, чтобы сделать наивный расчет.

Answer 3

В зависимости от интервьюера есть несколько ответов, которые могут быть приняты. И если какая-либо из них не будет принята, то, надеюсь, интервьюер быстро заставит вас предложить что-то еще.

• Использование gmp, и либо сделать свои подразделения и ХАРАКТЕРИСТИКИ с mpz_t вместо unsigned long или еще просто вычислить N^N и сравнить его с K. Это самое простое, что работает.
• Напишите свою собственную библиотеку большого числа, возможно, используя базу 10 как внутреннее представление, а не базу 2, если входные данные находятся в базе 10, и считается, что это может быть быстрее, чем преобразование в двоичный файл. Конечно, это не должна быть полная арифметическая библиотека, все, что вам действительно нужно, - это деление с остатком.
• Придумайте несколько быстрых тестов, которые вы можете сделать перед запуском, чтобы избежать большой работы, когда K в некотором отношении находится рядом с N^N. Например, проверьте, является ли log(K)/N приблизительно равным log(N), причем журнал, взятый в любой базе, наиболее удобен для ввода.Или проверить, сколько раз K и N, делятся на удобные номера типа 2 или 10: если K не делится ровно N раз столько раз, сколько N, то это явно не так. Или проверьте, равны ли они по модулю небольшому числу, например ULONG_MAX или 1000000. К сожалению, такие вещи только ускоряют определенные случаи, когда они не равны, это замедляет все остальное, включая случаи, когда они есть. Таким образом, это может быть контрпродуктивным, в зависимости от того, какие ресурсы вы ожидаете.

Ответ mcdowella может быть или не быть лучшим, я не знаю. Особенно многообещающе, что вам нужно только генерировать простые числа один раз (когда вы пишете программу), а 1000 простых чисел, начиная с 1009, более чем достаточны при условии N <= 1000. Большие простые значения означают меньше необходимых и, следовательно, меньше работы, особенно если они не становятся больше квадратного корня ULONG_MAX. Используйте возведение в степень по квадрату или эквиваленту, чтобы получить N^N по модулю каждого штриха, а для K выполните несколько цифр за раз в любой базе ввода.

Чтобы быть действительно вспыхивающим, для каждого из ваших предварительно выбранных чисел p вы можете написать (или позволить компилятору писать для вас) операцию modulo-p, которая быстрее, чем операция общего целочисленного модуля, которая работает для любого делителя. То есть, с достойным компилятором i % 1009 может быть быстрее, чем i % j, где значение j неизвестно во время компиляции, но получается во время выполнения 1009. Но будьте осторожны, разница в скорости может не оправдывать стоимость (скажем,), называя его указателем на функцию. Поэтому, пользуясь этим, может потребоваться некоторый уродливый повторяющийся код.

Answer 4

Даны два числа N и K такие, что 0 < = N < = 1000 и 0 < < = K = 1000^1000. Мне нужно проверить, что N^N = K или нет.

Многое зависит от того, как эти числа сохраняются при предоставлении кода. Предполагая, что они в текстовом формате, я просто сохранил их таким образом и создаю массив из 1001 строк, хранящих значения N^N. Вы можете использовать произвольную программу арифметической арифметической точности, например bc, для однократного создания этих строк, вызывая ее в цикле.

Answer 5

Так как из 1000^1000 (и они будут очень далеки друг от друга) будет иметься только 1000 «хороших» значений, вы могли бы использовать некоторую апроксимацию логарифма, чтобы иметь догадки для N. После этого вам понадобится не более одной точной проверки (например, с помощью некоторой библиотеки bignum).

Этот логарифм не обязательно должен быть точным, даже strlen() может быть достаточно приближенным.