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

Решение на основе набора ...

DECLARE @LastExponent smallint, @SearchCase decimal(38,0)

SELECT
    @LastExponent = 79, -- 38 for bigint
    @SearchCase = 729

;WITH CTE AS
(
    SELECT
        POWER(CAST(3 AS decimal(38,0)), ROW_NUMBER() OVER (ORDER BY c1.object_id)) AS Result,
        ROW_NUMBER() OVER (ORDER BY c1.object_id) AS Exponent
    FROM
        sys.columns c1, sys.columns c2
)
SELECT
    Result, Exponent
FROM
    CTE
WHERE
    Exponent <= @LastExponent
    AND
    Result = @SearchCase

С УСТАНОВИТЬ ВРЕМЯ СТАТИСТИКИ ВКЛ. записывается минимально возможное значение, 1 миллисекунда.

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

Алгоритм

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

Сложность:

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

For really large numbers n, you can use the following math trick to speed up the operation of

  n % 3 == 0

which is really slow and most likely the choke point of any algorithm that relies on repeated checking of remainders. You have to understand modular arithmetic to follow what I am doing, which is part of elementary number theory.

Let x = Σ _k a _k 2 ^k be the number of interest. We can let the upper bound of the sum be ∞ with the understanding that a _k = 0 for some k > M. Then

0 ≡ x ≡ Σ _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 (mod 3)

since 2^2k ≡ 4 ^k ≡ 1^k ≡ 1 (mod 3).

Given a binary representation of a number x with 2n+1 bits as

x₀ x₁ x₂ ... x_2n+1

where x_k ∈{0,1} you can group odd even pairs

(x₀ x₁) (x₂ x₃) ... (x_2n x_2n+1).

Let q denote the number of pairings of the form (1 0) and let r denote the number of pairings of the form (0 1). Then it follows from the equation above that 3 | x if and only if 3 | (q + 2r). Furthermore, you can show that 3|(q + 2r) if and only if q and r have the same remainder when divided by 3.

So an algorithm for determining whether a number is divisible by 3 could be done as follows

 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

This algorithm is more efficient than the use of %.

--- Edit many years later ----

I took a few minutes to implement a rudimentary version of this in python that checks its true for all numbers up to 10^4. I include it below for reference. Obviously, to make use of this one would implement this as close to hardware as possible. This scanning technique can be extended to any number that one wants to by altering the derivation. I also conjecture the 'scanning' portion of the algorithm can be reformulated in a recursive O(log n) type formulation similar to a FFT, but I'd have to think on it.

#!/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

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

Рекурсивно разделите на 3, проверьте, что остаток равен нулю, и повторно примените к частному.

Обратите внимание, что 1 является допустимым ответом, поскольку 3 в нулевой степени, 1 является ребром Остерегайтесь случая.

если (log n) / (log 3) является целым, то n является степенью 3.

while (n % 3 == 0) {
    n /= 3;
}
return n == 1;

Обратите внимание, что 1 - это нулевая степень тройки.

Изменить: Вам также необходимо проверить ноль перед циклом, так как цикл не завершится при n = 0 ( спасибо Бруно Ротгессеру).

На ваш вопрос довольно легко ответить, определив простую функцию, которая запускает проверку за вас. Показанный ниже пример реализации написан на 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 .

Я обнаружил, что слегка думаю, что если под «целым числом» вы имеете в виду «32-битное целое число со знаком», то (псевдокод)

return (n == 1) 
    or (n == 3)
    or (n == 9)
    ... 
    or (n == 1162261467) 

имеет определенная красивая простота (последнее число 3 ^ 19, так что абсурдного количества случаев нет). Даже для 64-битного целого числа без знака все равно будет всего 41 случай (спасибо @Alexandru за указание на мою ошибку). И, конечно, это было бы невозможно для арифметики произвольной точности ...

Очень интересный вопрос, мне нравится ответ от starblue , и это вариант его алгоритма, который немного быстрее сойдется к решению:

private bool IsPow3(int n)
{
    if (n == 0) return false;
    while (n % 9 == 0)
    {
        n /= 9;
    }
    return (n == 1 || n == 3);
}

Я удивлен этим. Кажется, все пропустили самый быстрый алгоритм из всех.

Следующий алгоритм в среднем быстрее - а в некоторых случаях и значительно быстрее - чем простой цикл while(n%3==0) n/=3; loop:

bool IsPowerOfThree(uint n)
{
  // Optimizing lines to handle the most common cases extremely quickly
  if(n%3 != 0) return n==1;
  if(n%9 != 0) return n==3;

  // General algorithm - works for any uint
  uint r;
  n = Math.DivRem(n, 59049, out r); if(n!=0 && r!=0) return false;
  n = Math.DivRem(n+r, 243, out r); if(n!=0 && r!=0) return false;
  n = Math.DivRem(n+r,  27, out r); if(n!=0 && r!=0) return false;
  n += r;
  return n==1 || n==3 || n==9;
}

Цифровые константы в коде 3^10, 3^5 и 3^3.

Вычисления производительности

В современных процессорах DivRem часто представляет собой единую команду, которая занимает один цикл. На других она расширяется до div, за которым следуют mul и add, что в целом больше похоже на три цикла. Каждый шаг общего алгоритма выглядит длинным, но на самом деле состоит только из него: DivRem, cmp, cmove, cmp, cand, cjmp, add. Параллельности много, поэтому на типичном двустороннем суперскалярном процессоре каждый шаг, скорее всего, будет выполняться примерно за 4 тактов, что дает гарантированное наихудшее время выполнения около 25 тактов.

Если входные значения равномерно распределены в диапазоне UInt32, то вот вероятности, связанные с этим алгоритмом:

• Возврат в или до первой оптимизирующей строки: 66% времени
• Возврат в или до второй оптимизирующей строки: 89% времени
• Возврат в или до первого общего шага алгоритма: 99. 998% времени
• Возврат на шаг второго общего алгоритма или до него: 99.99998% времени
• Возврат на шаг третьего общего алгоритма или до него: 99.999997% времени

Этот алгоритм превосходит простой цикл while(n%3==0) n/=3, который имеет следующие вероятности:

• Возврат в первой итерации: 66% времени
• Возвращение в первых двух итерациях: 89% времени
• Возврат в первых трех итерациях: 97% времени
• возврат в первых четырех итерациях: 98,8% времени
• Возвращение в первых пяти итерациях: 99,6% времени ... и так далее ...
• Возвращение в первых 12 итерациях: 99,9998% времени ... и далее ...

Что, пожалуй, еще более важно, этот алгоритм более эффективно обрабатывает средние и большие силы трех (и их кратные) намного : В худшем случае простой алгоритм будет потреблять более 100 процессорных циклов, так как зациклится 20 раз (41 раз на 64 бита). Представленный здесь алгоритм никогда не будет занимать более 25 циклов.

Расширение до 64 бит

Расширение вышеописанного алгоритма до 64 бит тривиально - просто добавьте еще один шаг. Приведем 64-битный вариант вышеуказанного алгоритма, оптимизированный для процессоров без эффективного 64-битного разделения:

bool IsPowerOfThree(ulong nL)
{
  // General algorithm only
  ulong rL;
  nL = Math.DivRem(nL, 3486784401, out rL); if(nL!=0 && rL!=0) return false;
  nL = Math.DivRem(nL+rL,   59049, out rL); if(nL!=0 && rL!=0) return false;
  uint n = (uint)nL + (uint)rL;
  n = Math.DivRem(n,   243, out r); if(n!=0 && r!=0) return false;
  n = Math.DivRem(n+r,  27, out r); if(n!=0 && r!=0) return false;
  n += r;
  return n==1 || n==3 || n==9;

}

Новая константа - 3^20. Строки оптимизации опущены сверху метода, так как при нашем предположении, что 64-битное деление медленное, они реально замедлят работу.

Почему работает этот метод

Скажем, я хочу знать, что "100000000000000000" - это мощность 10. Я могу следовать следующим шагам:

1. Я делюсь на 10^10 и получаю коэффициент 10000000 и остаток 0. Это прибавляет к 10000000.
2. Я делю на 10^5 и получаю коэффициент 100 и остаток 0. Они добавляют к 100.
3. Делаю на 10^3 и получаем коэффициент 0 и остаток 100. Они добавляют к 100.
4. Делаю на 10^2 и получаем коэффициент 1 и остаток 0. Добавляем к 1.

Поскольку я начинал с мощности 10, каждый раз, когда я делил мощность на 10, я получал либо нулевой коэффициент, либо нулевой остаток. Если бы я начинал с чего-нибудь, кроме мощности 10, то рано или поздно я бы заканчивал с ненулевым коэффициентом или остатком.

В этом примере я выбрал значения 10, 5 и 3, чтобы они совпадали с кодом, предоставленным ранее, и добавил 2 только для этого. Работали бы и другие экспоненты: Существует простой алгоритм выбора идеальных экспонентов, учитывая максимальное входное значение и максимальную мощность 10, разрешенную на выходе, но этого поля не хватает места, чтобы его содержать.

ПРИМЕЧАНИЕ: Возможно, вы думали в базе 10 в течение всего этого объяснения, но все объяснение выше можно прочитать и понять одинаково, если вы думаете в базе 3 , за исключением того, что экспоненты были бы выражены по-разному (вместо "10", "5", "3" и "2" мне пришлось бы сказать "101", "12", "10" и "2").