Задачка (разомнем мозги :))

[Clear_Mind]

Простенькая задачка
В теории чисел существует такое понятие как символ Лежандра
Так вот, при вычислении этого символа встает задача вычисления
выражения k = (-1)^((a^2 - 1)/8), причем а -- простое большее 2.
Необходимо оптимизировать вычисление этого выражения не забыв про
то, что а может быть любых размеров (вплоть до максимального простого
влезающего в long)

[backslash]

a = 4*p +(-) 1, p - натуральное,
8*x = a^2 - 1 = 16*p^2 +(-) 8*p = 8*p*(2*p +(-) 1),
x = p*(2*p +(-) 1),
т.е. четность показателя степени определяется четностью p.
Поэтому делим a на 4, округляя в сторону ближайшего целого (a>2 - простое => a = 4*p +(-) 1).
Если получается четное число - k=1, если нечетное - k=-1. Верно?

[Clear_Mind]

a = 4*p +(-) 1, p - натуральное,
8*x = a^2 - 1 = 16*p^2 +(-) 8*p = 8*p*(2*p +(-) 1),
x = p*(2*p +(-) 1),
т.е. четность показателя степени определяется четностью p.
Поэтому делим a на 4, округляя в сторону ближайшего целого (a>2 - простое => a = 4*p +(-) 1).
Если получается четное число - k=1, если нечетное - k=-1. Верно?

(a>2 - простое => a = 4*p +(-) 1) --- сомневаюсь <_<
А вообще как-то все слишком сложно
Есть более простое (и правильное) решение.

[backslash]

(a>2 - простое => a = 4*p +(-) 1) --- сомневаюсь

Почему же? Делим a на 4, в остатке получаем либо 1, либо 3 (иначе a четно), т.е. a=4*p+1 либо a=4*p+3=4*(p+1)-1, как я и написал.

А вообще как-то все слишком сложно
Есть более простое (и правильное) решение.

Проще, чем поделить на четыре, округлить и проверить четность результата?

[Egan]

Я думаю имеется ввиду, что для больших чисел такое деление будет не оптимальным решением.
Собственно k будет равно 1, если делится на 8 одно из двух трёхзначных чисел, составленных из разрядов (сотен, десятков и единиц) чисел a - 1 и a + 1. То есть достаточно брать не всё число, а только три правых его цифры.

[backslash]

Я думаю имеется ввиду, что для больших чисел такое деление будет не оптимальным решением.

Ну, я предложил математическую основу решения. Техника "делить - не делить" - это уже дело второе.

[Clear_Mind]

Проще, чем поделить на четыре, округлить и проверить четность результата?

Проще для компьютера (мы ведь оптимизиуем вычисление).
Да и для пограммиста довольно просто.

ЗЫ подождем еще вариантов (если они будут)

Ну, я предложил математическую основу решения. Техника "делить - не делить" - это уже дело второе.

Есть более простое и сточки зрения математики решение

[Clear_Mind]

Решение основывается на простом факте, что выражение a^2-1 всегда делится нацело на 8, что в свою
чередь означает, что a^2 в двоичнов виде представляется как ХХ...ХХ001, где Х -- двоичная цифра
(1|0), и следовательно четность показателя степени зависит от 4-го двоичного разряда числа a^2. В
результате вычисление сведется к

Код: Выделить всё

k = 1;
if( (a*a)&8 ) k = -k;

все просто.

[Egan]

Уточняющий вопрос:
Если a - максимальное простое влезающее в long, сможет ли компьютер обработать a*a?

[Clear_Mind]

Хороший вопрос, а ответ на него ДА
Даже не придется с ассемблером париться.

На компьютерах x86 в том числе х86_64, для умножения используются два регистра eax (rax), edx (rdx)
при умножении чисел, если результат не помещается в ax, то его младшая часть (та в которую входит четвертый бит) помещается в eax, а старшая в edx/
Следовательно какое бы не было по размеру число а, компилятор всегда сгенерирует правильно работающий код.

проверял.

[v04bvs]

Уточняющий вопрос:
Если a - максимальное простое влезающее в long, сможет ли компьютер обработать a*a?

может быть переполнение.

[Clear_Mind]

может быть переполнение.

Нет, как я убедился на нескольких компиляторах переполнение не возникает.
К примеру вполне реально производить следующие вычисления:
a=(b*c)%d;
без потери информации не зависимо от величины b и c, но в данном случае я бы не стал гарантировать, что компилятор сгенерирует правильный код (к примеру он может поместить рез-т b*c во временную переменную и потерять часть рез-тата).

Но задача приведенная выше вполне переносимо решается приведенным мной способом.

[aLexx programmer]

Нет, как я убедился на нескольких компиляторах переполнение не возникает.

↑

"На нескольких" - не значит "на всех".

[Clear_Mind]

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

младшая часть лежит в rax, следующие вычисления сведутся к двоичному сдвигу, и коньюнкции этого же регистра

[Clear_Mind]

Привожу пример

Код: Выделить всё

long f(long a) {
    return (a*a)&8;
}

int main() { f(742300010101); }

получаю

Код: Выделить всё

; непосредственно тело вункции (получил через g++ -S tt.cpp)
movq    %rdi, -8(%rbp);получаем аргумент ф-и
movq    -8(%rbp), %rax;ложим арг в rax
imulq    -8(%rbp), %rax;умножаем арг на rax (a*a)
andl    $8, %eax; коньюнкция
; обратите внимание, что он даже не совсем регистром выполняет коньюнкцию
; а с его младшей частью eax
; (rax - 64bit, eax - 32bit)
leave
ret

ЗЫ: я с вами согласен, что на такие вещи полагаться не стоит, но все же решение красивое и не лишино смысла.
ЗЗЫ: спасибо всем!

[v04bvs]

Код: Выделить всё

% cat test.cpp
#include <limits>
#include <iostream>

int main()
{
    long a = std::numeric_limits<long>::max();
    long b = (a * a) % 17;

    long long a2 = (long long)a * a;

    std::cout << "a = " << a << " a^2 = " << a2 << std::endl <<
    "b = " << b << " a^2 % 17 = " << (a2 % 17) << std::endl;

    return 0;
}
% ./test
a = 2147483647 a^2 = 4611686014132420609
b = 1 a^2 % 17 = 13

Так что переполнение вполне может быть.
На всякий случай сообщаю, у меня обычный Pentium 4.

[Clear_Mind]

К примеру вполне реально производить следующие вычисления:
a=(b*c)%d;
без потери информации не зависимо от величины b и c, но в данном случае я бы не стал гарантировать, что компилятор сгенерирует правильный код (к примеру он может поместить рез-т b*c во временную переменную и потерять часть рез-тата).

v04bvs все правильно, b считается способом отличным от a2%17, т.к. я уже говорил выше.

Код: Выделить всё

b = (a*a)%17; /* рез-т произведения ложится в два регистра (eax и edx на 32bit компе)
если сразу же производить деление, то делиться будет все  число (которое находится в 2-х рег-х)
после деления частное -- eax, остаток -- edx
в данном конкретном примере остаток может оказаться вполне правильным (если компилер не вставил какие-либо еще команды между произведением и делением)*/

long long a2 = (long long)a * a; /* а2 сразу ложится в отдельную переменную, что приводит к потери той части, которая лежала в edx (старш. часть)*/

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

Код: Выделить всё

#include <iostream>
#include <limits>

using namespace std;

int main() {
    long a = numeric_limits<long>::max();
    long k;
            long long k2;
    for(a; a > 0; --a) {
        k = (a*a)&8;
        k2 = a*a;
        k2 &= 8;
//         if(k) cout << '*'; что бы убедиться, что равномерно появляются и 1 и 0
//         else cout << ' ';
        if(k != k2) break; //выйти из цикла если ошибка
    }
    cout << k << ' ' << k2 << endl;

}

ЗЫ: в правильности вышесказанного я убедился и на P4 и на Athlon64
ЗЗЫ: пока писал ответ программа работала (уже около 15 мин)

[diafour]

Так если нужен только 4-ый младший бит квадрата числа, то зачем вычислять квадрат от полного a?
Достаточно будет

if (( a&15 * a&15) & 8 ) k = -k;

[Egan]

Предлагаю другой вариант решения. Одно из двух чисел a-1 и a+1 делится на 2 и не делится на 4, а другое точно делится и на 4. Если то, которое делится на 4 будет делится и на 8 k=1, в противном случае k=-1.
a-1 делится на 8, если a равно в двоичной системе X...XX001
a+1 делится на 8, если a равно в двоичной системе X...XX111
То есть надо проверить, чтобы у a совпадали второй и третий разряды.

k=-1;
if ( (a&2) == (a&4) ) k = -k;