Быстрое вычисление наибольшего общего делителя для unsigned long long int

@taras atavin · Регистрация: 24.11.2009

Даны два числа типа unsigned long long int, в них могут оказаться любые представимые значения, требуется максимально быстро вычислить наибольший общий делитель.

@SlavaSSU · 01.12.2014, 09:01

taras atavin, я может туплю(скорее всего), но чем Евклид не подходит?

@taras atavin · 01.12.2014, 10:29 **[ТС]**

А при чём здесь геометрия? Или Вы о чём?

Croessmah · 01.12.2014, 10:32

Сообщение от taras atavin

Или Вы о чём?

Википедия: Алгоритм Евклида

@taras atavin · 01.12.2014, 10:57 **[ТС]**

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

Одно число 2 701 703 435 345 984 178, второе 15, искомое число 3. Сколько раз вычитать будем? А перебирать все меньшие числа плохо, когда оба числа большие.

@SlavaSSU · 01.12.2014, 11:03

C++ (Qt)

#include <iostream>
 
using namespace std;
 
typedef unsigned long long uli;
 
uli gcd(uli a, uli b)
{
    if(b == 0)
        return a;
    return gcd(b, a % b);
}
 
int main(){
 
    uli a, b;
    cin >> a >> b;
    uli g = gcd(a, b);
    cout << g << endl;
 
    return 0;
}

если из числа А много раз вычитать число Б пока оно не станет меньше, в итоге получим число А % Б.

@taras atavin · 01.12.2014, 12:35 **[ТС]**

Сообщение от SlavaSSU

uli gcd(uli a, uli b) { if(b == 0) return a; return gcd(b, a % b); }

Какова максимальная глубина рекурсии?

Добавлено через 5 минут
И может тогда уж так:

C++

unsigned long long int nod(unsigned long long int a, unsigned long long int b)
{
 unsigned long long int c;
 if (a<b)
 {
  c=a;
  a=b;
  b=c;
 }
 while (b!=0)
 {
  c=a%b;
  a=b;
  b=c;
 }
 return a;
}

.

Добавлено через 5 минут
Вторая версия задачи. Даны четыре числа: a, b, c и d. Все четыре типа unsigned long long int и могут иметь любые представимые значения, но с одним ограничением: наибольший общий делителитель a и b равен 1 и наибольший общий делитель c и d равен 1. Требуется найти наибольший общий делитель произведений a*b и c*d (разрядностью по 128 бит каждое), но в явном виде эти произведения не вычислять.

@SlavaSSU · 01.12.2014, 13:41

taras atavin, да без разницы рекурсивно писать или нет, все равно он быстро работает. там вроде O(log(log(max(a, b))) он работает евклид.

насчет второго есть предположение.

C++ (Qt)

#include <iostream>
#include <cassert>
 
using namespace std;
 
typedef unsigned long long uli;
 
uli gcd(uli a, uli b)
{
    if(b == 0)
        return a;
    return gcd(b, a % b);
}
 
uli naive(uli a, uli b, uli c, uli d)
{
    return gcd(a * b, c * d);
}
 
int main(){
 
    uli a, b, c, d;
    cin >> a >> b >> c >> d;
    assert(gcd(a, b) == 1);
    assert(gcd(c, d) == 1);
 
    uli g = gcd(a, c) * gcd(a, d) * gcd(b, c) * gcd(b, d);
    cout << "answer is " << gcd(a, c) << " * " << gcd(a, d) << " * " << gcd(b, c) << " * " << gcd(b, d) << endl;
    cout << g << endl;
    cerr << naive(a, b, c, d) << endl;
 
    return 0;
}

Добавлено через 6 минут
я наврал. перепутал с другим. за log(min(a, b)) работает евклид. ну все равно быстро.

@taras atavin · 01.12.2014, 13:44 **[ТС]**

Сообщение от SlavaSSU

uli naive(uli a, uli b, uli c, uli d) { return gcd(a * b, c * d); }

При вычислении произведений может произойти переполнение типа. Поэтому условие:

Сообщение от taras atavin

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

. В то же время a может иметь достаточно большой общий делитель с d, а с хорошо делиться на b.

Добавлено через 1 минуту

Сообщение от SlavaSSU

я наврал. перепутал с другим. за log(min(a, b)) работает евклид. ну все равно быстро.

То есть максимум десятки шагов цикла?

@SlavaSSU · 01.12.2014, 13:48

taras atavin, я понимаю что там все переполнится. это я тестил ччуть-чуть на небольших числах.

ну да, для чисел порядка 10^18 - 60 шагов. грубо говоря.

@taras atavin · 01.12.2014, 13:51 **[ТС]**

Сообщение от SlavaSSU

uli a, b, c, d; cin >> a >> b >> c >> d; assert(gcd(a, b) == 1); assert(gcd(c, d) == 1);

Ты не понял. Числа не сами по себе, это числитель и знаменатель дроби и она уже сокращена. Задачи такие:
1. Упростить обыкновенную дробь, представленную числителем и знаменателем типа unsigned long long int.
2. Вычислить числитель и знаменатель упрощённой обыкновенной дроби, равной произведению двух дургих упрощённых обыкновенных дробей.
НОД=1 именно потому, что операнды уже упрощены. Поэтому ни какого ассерта, просто a и b заранее поделены на наибольший общий делитель этой пары, а c и d заранее поделены на наибольший общий делитель второй пары.

@SlavaSSU · 01.12.2014, 13:54

taras atavin, просто привычка иногда проверять входные данные на корректность.

@taras atavin · 01.12.2014, 14:03 **[ТС]**

Сообщение от SlavaSSU

taras atavin, просто привычка иногда проверять входные данные на корректность.

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

@taras atavin 4202 / 1794 / 211 Регистрация: 24.11.2009 Сообщений: 27,562
		1
	Быстрое вычисление наибольшего общего делителя для unsigned long long int 01.12.2014, 08:02. Показов 1324. Ответов 12 Метки нет (Все метки) Даны два числа типа unsigned long long int, в них могут оказаться любые представимые значения, требуется максимально быстро вычислить наибольший общий делитель. 0

@SlavaSSU 220 / 165 / 47 Регистрация: 17.07.2012 Сообщений: 587
	01.12.2014, 09:01	2
	taras atavin, я может туплю(скорее всего), но чем Евклид не подходит? 0

@taras atavin 4202 / 1794 / 211 Регистрация: 24.11.2009 Сообщений: 27,562
	01.12.2014, 10:29 [ТС]	3
	А при чём здесь геометрия? Или Вы о чём? 0

Croessmah Don't worry, be happy 17781 / 10545 / 2035 Регистрация: 27.09.2012 Сообщений: 26,514 Записей в блоге: 1
	01.12.2014, 10:32	4
	Сообщение от taras atavin Или Вы о чём? Википедия: Алгоритм Евклида 0

@taras atavin 4202 / 1794 / 211 Регистрация: 24.11.2009 Сообщений: 27,562
	01.12.2014, 10:57 [ТС]	5
	В самом простом случае алгоритм Евклида применяется к паре положительных целых чисел и формирует новую пару, которая состоит из меньшего числа и разницы между большим и меньшим числом. Процесс повторяется, пока числа не станут равными. Найденное число и есть наибольший общий делитель исходной пары. Одно число 2 701 703 435 345 984 178, второе 15, искомое число 3. Сколько раз вычитать будем? А перебирать все меньшие числа плохо, когда оба числа большие. 0

@taras atavin 4202 / 1794 / 211 Регистрация: 24.11.2009 Сообщений: 27,562
	01.12.2014, 13:44 [ТС]	9
	Сообщение от SlavaSSU uli naive(uli a, uli b, uli c, uli d) { return gcd(a * b, c * d); } При вычислении произведений может произойти переполнение типа. Поэтому условие: Сообщение от taras atavin но в явном виде эти произведения не вычислять. . В то же время a может иметь достаточно большой общий делитель с d, а с хорошо делиться на b. Добавлено через 1 минуту Сообщение от SlavaSSU я наврал. перепутал с другим. за log(min(a, b)) работает евклид. ну все равно быстро. То есть максимум десятки шагов цикла? 0

@SlavaSSU 220 / 165 / 47 Регистрация: 17.07.2012 Сообщений: 587
	01.12.2014, 13:48	10
	taras atavin, я понимаю что там все переполнится. это я тестил ччуть-чуть на небольших числах. ну да, для чисел порядка 10^18 - 60 шагов. грубо говоря. 0

@taras atavin 4202 / 1794 / 211 Регистрация: 24.11.2009 Сообщений: 27,562
	01.12.2014, 13:51 [ТС]	11
	Сообщение от SlavaSSU uli a, b, c, d; cin >> a >> b >> c >> d; assert(gcd(a, b) == 1); assert(gcd(c, d) == 1); Ты не понял. Числа не сами по себе, это числитель и знаменатель дроби и она уже сокращена. Задачи такие: 1. Упростить обыкновенную дробь, представленную числителем и знаменателем типа unsigned long long int. 2. Вычислить числитель и знаменатель упрощённой обыкновенной дроби, равной произведению двух дургих упрощённых обыкновенных дробей. НОД=1 именно потому, что операнды уже упрощены. Поэтому ни какого ассерта, просто a и b заранее поделены на наибольший общий делитель этой пары, а c и d заранее поделены на наибольший общий делитель второй пары. 0

@SlavaSSU 220 / 165 / 47 Регистрация: 17.07.2012 Сообщений: 587
	01.12.2014, 13:54	12
	taras atavin, просто привычка иногда проверять входные данные на корректность. 0

@taras atavin 4202 / 1794 / 211 Регистрация: 24.11.2009 Сообщений: 27,562
	01.12.2014, 14:03 [ТС]	13
	Сообщение от SlavaSSU taras atavin, просто привычка иногда проверять входные данные на корректность. Для задачи они корректны и при несоответствии указанному ограничению. Ограничение возникло просто из порядка решения указанных задач. Все четыре лежат в двух приватных полях двух объектов, поля присваиваются только конструктором, он сначала считает НОД, потом делит на него оба числа и только после этого присваиваются. 0

Опции темы