Как проверить, является ли целое число степенью 3? - PullRequest
Новая
       62

Как проверить, является ли целое число степенью 3?

44 голосов
/ 26 ноября 2009

Я видел этот вопрос , и всплыла эта идея.

Ответы [ 23 ]

4 голосов
/ 26 ноября 2009

Насколько велик ваш вклад? С O (log (N)) памяти вы можете делать быстрее, O (log (log (N)). Предварительно вычислить степени 3 и затем выполнить двоичный поиск по предварительно вычисленным значениям.

4 голосов
/ 01 мая 2013

Вот хорошая и быстрая реализация метода Рэй Бернса в C: 

bool is_power_of_3(unsigned x) {
    if (x > 0x0000ffff)
        x *= 0xb0cd1d99;    // multiplicative inverse of 59049
    if (x > 0x000000ff)
        x *= 0xd2b3183b;    // multiplicative inverse of 243
    return x <= 243 && ((x * 0x71c5) & 0x5145) == 0x5145;
}

Используется мультипликативный трюк , чтобы сначала разделить на 3 ^ 10, а затем на 3 ^ 5. Наконец, он должен проверить, равен ли результат 1, 3, 9, 27, 81 или 243, что делается с помощью простого хеширования, которое я нашел методом проб и ошибок.

На моем процессоре (Intel Sandy Bridge) он довольно быстрый, но не такой быстрый, как метод starblue, который использует двоичный логарифм (который реализован в аппаратном обеспечении на этом процессоре). Но на процессоре без такой инструкции или когда таблицы поиска нежелательны, это может быть альтернативой.

4 голосов
/ 27 ноября 2009

Для действительно больших чисел n, вы можете использовать следующий математический трюк, чтобы ускорить операцию 

  n % 3 == 0

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

Пусть х = & Сигма; k a k 2 k будет числом интереса. Мы можем позволить верхней границе суммы быть & бесконечным; с пониманием, что a k = 0 для некоторого k> M. Тогда

0 & экв .; х & экв; &Сигма; k a k 2 k & экв .; &Сигма; k a 2k 2 2k + a 2k + 1 2 2k + 1 и эквивалент; &Сигма; k 2 2k (a 2k + a 2k + 1 2) и эквивалент; &Сигма; k a 2k + a 2k + 1 2 (мод 3)

с 2 2k & экв .; 4 k & экв .; 1 k & экв .; 1 (мод 3).

Дано двоичное представление числа x с 2n + 1 битами как

x 0 x 1 x 2 ... x 2n + 1

где x k & isin; {0,1} вы можете сгруппировать нечетные четные пары

(x 0 x 1 ) (x 2 x 3 ) ... (x 2n x 2n + 1 ).

Пусть q обозначает количество пар вида (1 0), а r обозначает количество пар вида (0 1). Тогда из приведенного выше уравнения следует, что 3 | х тогда и только тогда, когда 3 | (q + 2r). Кроме того, вы можете показать, что 3 | (q + 2r) тогда и только тогда, когда q и r имеют одинаковый остаток при делении на 3.

Таким образом, алгоритм для определения, делится ли число на 3, можно сделать следующим образом 

 q = 0, r = 0
 for i in {0,1, .., n}
     pair <- (x_{2i} x_{2i+1})
     if pair == (1 0)
         switch(q)
             case 0:
                 q = 1;
                 break;
             case 1:
                 q = 2;
                 break;
             case 2:
                 q = 0;
                 break;
     else if pair == (0 1)
         switch(r)
             case 0:
                 r = 1;
                 break;
             case 1:
                 r = 2;
                 break;
             case 2:
                 r = 0;
 return q == r

Этот алгоритм более эффективен, чем использование%.

--- Редактировать много лет спустя ----

Мне потребовалось несколько минут, чтобы реализовать элементарную версию этого в python, которая проверяет его истинность для всех чисел до 10 ^ 4. Я включаю это ниже для справки. Очевидно, что использование этого будет реализовывать это как можно ближе к аппаратному обеспечению. Эту технику сканирования можно распространить на любое число, которое нужно, изменив вывод. Я также предполагаю, что «сканирующая» часть алгоритма может быть переформулирована в рекурсивной формулировке типа O(log n), похожей на БПФ, но я должен подумать над этим. 

#!/usr/bin/python

def bits2num(bits):
    num = 0
    for i,b in enumerate(bits):
        num += int(b) << i
    return num

def num2bits(num):
    base = 0
    bits = list()
    while True:
        op = 1 << base
        if op > num:
            break
        bits.append(op&num !=0)
        base += 1
    return "".join(map(str,map(int,bits)))[::-1]

def div3(bits):

    n = len(bits)

    if n % 2 != 0:
        bits = bits + '0'

    n = len(bits)

    assert n % 2 == 0

    q = 0
    r = 0
    for i in range(n/2):
        pair = bits[2*i:2*i+2]
        if pair == '10':
            if q == 0:
                q = 1
            elif q == 1:
                q = 2
            elif q == 2:
                q = 0
        elif pair == '01':
            if r == 0:
                r = 1
            elif r == 1:
                r = 2
            elif r == 2:
                r = 0
        else:
            pass

    return q == r

for i in range(10000):
    truth = (i % 3)  == 0
    bits = num2bits(i)
    check  = div3(bits)
    assert truth == check
3 голосов
/ 11 января 2017

Самым быстрым решением является либо проверка, если n > 0 && 3**19 % n == 0, как указано в другой ответ , либо идеальное хеширование (ниже). Сначала я даю два решения на основе умножения.

Умножение

Интересно, почему все пропустили, что умножение намного быстрее, чем деление: 

for (int i=0, pow=1; i<=19, pow*=3; ++i) {
    if (pow >= n) {
        return pow == n;
    }
}
return false;

Просто попробуй все силы, остановись, когда она станет слишком большой. Избегайте переполнения, так как 3**19 = 0x4546B3DB - самый большой силовой фитинг в 32-битном int со знаком.

Умножение с бинарным поиском

Двоичный поиск может выглядеть как 

int pow = 1;
int next = pow * 6561; // 3**8
if (n >= next) pow = next;
next = pow * 81; // 3**4
if (n >= next) pow = next;
next = pow * 81; // 3**4; REPEATED
if (n >= next) pow = next;
next = pow * 9; // 3**2
if (n >= next) pow = next;
next = pow * 3; // 3**1
if (n >= next) pow = next;
return pow == next;

Один шаг повторяется, так что максимальный показатель 19 = 8+4+4+2+1 может быть точно достигнут.

Идеальное хеширование

Есть 20 степеней трех, вписывающихся в 32-битное целое со знаком, поэтому мы возьмем таблицу из 32 элементов. С некоторыми экспериментами я нашел идеальную хеш-функцию 

def hash(x):
    return (x ^ (x>>1) ^ (x>>2)) & 31;

отображение каждой степени в отдельный индекс от 0 до 31. Остальные вещи тривиальны: 

// Create a table and fill it with some power of three.
table = [1 for i in range(32)]
// Fill the buckets.
for n in range(20): table[hash(3**n)] = 3**n;

Теперь у нас есть 

table = [
     1162261467, 1, 3, 729, 14348907, 1, 1, 1,
     1, 1, 19683, 1, 2187, 81, 1594323, 9,
     27, 43046721, 129140163, 1, 1, 531441, 243, 59049,
     177147, 6561, 1, 4782969, 1, 1, 1, 387420489]

и может тестировать очень быстро с помощью 

def isPowerOfThree(x):
    return table[hash(x)] == x
3 голосов
/ 26 ноября 2009

Вы можете сделать лучше, чем повторное деление, которое занимает O (LG (X) * | Деление |) время. По сути, вы выполняете двоичный поиск по степеням 3. Действительно, мы будем выполнять двоичный поиск по N, где 3 ^ N = входное значение). Установка двоичной цифры Pth для N соответствует умножению на 3 ^ (2 ^ P), а значения вида 3 ^ (2 ^ P) можно вычислить путем повторного возведения в квадрат.

Алгоритм

  • Пусть входным значением будет X.
  • Создает список L повторяющихся квадратов значений, который заканчивается, как только вы передаете X.
  • Пусть значение вашего кандидата будет T, инициализировано в 1.
  • Для каждого E в обращенном L, если T * E <= X, тогда пусть T * = E. </li>
  • Return T == X.

Сложность:

O (lg (lg (X)) * | умножение |) - Генерация и итерация по L требует итераций lg (lg (X)), а умножение является самой дорогой операцией в итерации.

1 голос
/ 26 ноября 2009

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

Python 3.6.0 (v3.6.0:41df79263a11, Dec 23 2016, 08:06:12) [MSC v.1900 64 bit (AMD64)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> import math
>>> def power_of(number, base):
    return number == base ** round(math.log(number, base))

>>> base = 3
>>> for power in range(21):
    number = base ** power
    print(f'{number} is '
          f'{"" if power_of(number, base) else "not "}'
          f'a power of {base}.')
    number += 1
    print(f'{number} is '
          f'{"" if power_of(number, base) else "not "}'
          f'a power of {base}.')
    print()


1 is a power of 3.
2 is not a power of 3.

3 is a power of 3.
4 is not a power of 3.

9 is a power of 3.
10 is not a power of 3.

27 is a power of 3.
28 is not a power of 3.

81 is a power of 3.
82 is not a power of 3.

243 is a power of 3.
244 is not a power of 3.

729 is a power of 3.
730 is not a power of 3.

2187 is a power of 3.
2188 is not a power of 3.

6561 is a power of 3.
6562 is not a power of 3.

19683 is a power of 3.
19684 is not a power of 3.

59049 is a power of 3.
59050 is not a power of 3.

177147 is a power of 3.
177148 is not a power of 3.

531441 is a power of 3.
531442 is not a power of 3.

1594323 is a power of 3.
1594324 is not a power of 3.

4782969 is a power of 3.
4782970 is not a power of 3.

14348907 is a power of 3.
14348908 is not a power of 3.

43046721 is a power of 3.
43046722 is not a power of 3.

129140163 is a power of 3.
129140164 is not a power of 3.

387420489 is a power of 3.
387420490 is not a power of 3.

1162261467 is a power of 3.
1162261468 is not a power of 3.

3486784401 is a power of 3.
3486784402 is not a power of 3.

>>>

ПРИМЕЧАНИЕ: Последняя редакция привела к тому, что этот ответ стал почти таким же, как TMS 'ответ .

0 голосов
/ 29 апреля 2018

Я измерял время (C #, целевая платформа x64) для некоторых решений. 

using System;
class Program
{
    static void Main()
    {
        var sw = System.Diagnostics.Stopwatch.StartNew();
        for (uint n = ~0u; n > 0; n--) ;
        Console.WriteLine(sw.Elapsed);              // nada   1.1 s
        sw.Restart();
        for (uint n = ~0u; n > 0; n--) isPow3a(n);
        Console.WriteLine(sw.Elapsed);              // 3^20  17.3 s
        sw.Restart();
        for (uint n = ~0u; n > 0; n--) isPow3b(n);
        Console.WriteLine(sw.Elapsed);              // % /   10.6 s
        Console.Read();
    }

    static bool isPow3a(uint n)  // Elric
    {
        return n > 0 && 3486784401 % n == 0;
    }

    static bool isPow3b(uint n)  // starblue
    {
        if (n > 0) while (n % 3 == 0) n /= 3;
        return n == 1;
    }
}

Другой способ (расщепления волос). 

using System;
class Program
{
    static void Main()
    {
        Random rand = new Random(0); uint[] r = new uint[512];
        for (int i = 0; i < 512; i++)
            r[i] = (uint)(rand.Next(1 << 30)) << 2 | (uint)(rand.Next(4));
        var sw = System.Diagnostics.Stopwatch.StartNew();
        for (int i = 1 << 23; i > 0; i--)
            for (int j = 0; j < 512; j++) ;
        Console.WriteLine(sw.Elapsed);                    //   0.3 s
        sw.Restart();
        for (int i = 1 << 23; i > 0; i--)
            for (int j = 0; j < 512; j++) isPow3c(r[j]);
        Console.WriteLine(sw.Elapsed);                    //  10.6 s
        sw.Restart();
        for (int i = 1 << 23; i > 0; i--)
            for (int j = 0; j < 512; j++) isPow3b(r[j]);
        Console.WriteLine(sw.Elapsed);                    //   9.0 s
        Console.Read();
    }

    static bool isPow3c(uint n)
    { return (n & 1) > 0 && 3486784401 % n == 0; }

    static bool isPow3b(uint n)
    { if (n > 0) while (n % 3 == 0) n /= 3; return n == 1; }
}
0 голосов
/ 02 мая 2016

Это метод с постоянным временем! Да. O (1). Для чисел фиксированной длины, скажем, 32-разрядных.

Учитывая, что нам нужно проверить, является ли целое число n степенью 3, давайте начнем думать об этой проблеме с точки зрения того, какая информация уже имеется.

1162261467 - это наибольшая степень 3, которая может вписаться в Java int.
1162261467 = 3^19 + 0

Данную n можно выразить как [(степень 3) + (некоторая x)]. Я думаю, что это довольно элементарно - доказать, что если x равно 0 (что случается , если n - это степень 3), 1162261467% n = 0.

Общая идея состоит в том, что если X - некоторая степень 3, X может быть выражен как Y/3a, где a - некоторое целое число и X

Итак, чтобы проверить, является ли данное целое число n степенью три, проверьте, если n > 0 && 1162261467 % n == 0.

0 голосов
/ 24 марта 2016 
#include<iostream>
#include<string>
#include<cmath>
using namespace std;
int main()
{
     int n, power=0;
      cout<<"enter a number"<<endl;
      cin>>n;
  if (n>0){

     for(int i=0; i<=n; i++)
     {

         int r=n%3;

            n=n/3;
         if (r==0){
            power++;
         }

         else{
               cout<<"not exactly power of 3";
                return 0;

             }
     }

   }

         cout<<"the power is "<<power<<endl;
  }
0 голосов
/ 20 июля 2015

Другой подход заключается в создании таблицы времени компиляции. Хорошо, что вы можете расширить это до степеней 4, 5, 6, 7, независимо от того, 

template<std::size_t... Is>
struct seq
{  };

template<std::size_t N, std::size_t... Is>
struct gen_seq : gen_seq<N-1, N-1, Is...>
{  };

template<std::size_t... Is>
struct gen_seq<0, Is...> : seq<Is...>
{  };

template<std::size_t N>
struct PowersOfThreeTable
{
    std::size_t indexes[N];
    std::size_t values[N];

    static constexpr std::size_t size = N;
};

template<typename LambdaType, std::size_t... Is>
constexpr PowersOfThreeTable<sizeof...(Is)>
    generatePowersOfThreeTable(seq<Is...>, LambdaType evalFunc)
{
    return { {Is...}, {evalFunc(Is)...} };
}

template<std::size_t N, typename LambdaType>
constexpr PowersOfThreeTable<N> generatePowersOfThreeTable(LambdaType evalFunc)
{
    return generatePowersOfThreeTable(gen_seq<N>(), evalFunc);
}

template<std::size_t Base, std::size_t Exp>
struct Pow
{
    static constexpr std::size_t val = Base * Pow<Base, Exp-1ULL>::val;
};

template<std::size_t Base>
struct Pow<Base, 0ULL>
{
    static constexpr std::size_t val = 1ULL;
};

template<std::size_t Base>
struct Pow<Base, 1ULL>
{
    static constexpr std::size_t val = Base;
};

constexpr std::size_t tableFiller(std::size_t val)
{ 
    return Pow<3ULL, val>::val;
}

bool isPowerOfThree(std::size_t N)
{
    static constexpr unsigned tableSize = 41; //choosen by fair dice roll

    static constexpr PowersOfThreeTable<tableSize> table = 
            generatePowersOfThreeTable<tableSize>(tableFiller);

    for(auto a : table.values)
        if(a == N)
            return true;
    return false;
}
Страница:
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Нет похожих вопросов

...