Как выполнить сложение по модулю 2^64+13

@rudeeeboy · Регистрация: 08.11.2010

Author24 — интернет-сервис помощи студентам

Всем привет, есть два 64 битовых числа, как можно сделать сложение по модулю mod(2^64+13)?

@nmcf · 14.12.2014, 15:34

По какому модулю?

@rudeeeboy · 14.12.2014, 15:37 **[ТС]**

вот полное выражение
x=(((a*m+b)mod(2^64+13))mod(2^64)

@nmcf · 14.12.2014, 15:41

Я говорю, mod - это что за функция? И что такое ^ в твоей записи?

@rudeeeboy · 14.12.2014, 15:44 **[ТС]**

mod - модуль
^ - степень

@nmcf · 14.12.2014, 15:51

Модуль числа - функция abs().
Возведение в степень для двойки 2^64 через сдвиг 1 << 64.

C++
1
abs((1 << 64) + 13)

Если я правильно понял твою запись.

@AleksRazgul · 14.12.2014, 16:08

nmcf Я сомневаюсь что такой вариант прокатит.
Мне кажется что в результате получится 0, если компилятор будет использовать 32-x битное или 64-x битное значение. То что он будет использовать 128-ми битное значение я сомневаюсь.

Добавлено через 6 минут
для возведения в степень лучше использовать pow(значение, степень)

@gunslinger · 14.12.2014, 16:11

mod здесь скорей всего остаток от деления, пусть и называется модулем.

@rudeeeboy · 14.12.2014, 16:32 **[ТС]**

так что делать тогда с mod(2^64+13)?
я пытаюсь реализовать этот алгоритм https://ru.wikipedia.org/wiki/DFC

@nmcf · 14.12.2014, 17:37

Ну я подумал, что здесь целочисленная арифметика. Если нет, то, разумеется, pow().

@Гром · 14.12.2014, 18:19

Самый простой и наглядный способ - использовать длинную арифметику (гуглим "длинная арифметика"). Возможно, существуют способы получить результат, использую 32- или 64-битные целые, но они, вероятно, будут гораздо более сложными для понимания и/или реализации.

@Renji · 14.12.2014, 18:24

C++
1
2
3
4
long double a=1234,b=5678;
const long double mod=18446744073709551629.0;
double res=a+b;
cout<<(res<mod?res:res-mod)<<endl;

@Гром · 14.12.2014, 18:43

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

C++
1
2
3
4
long double a=1234,b=5678;
const long double mod=18446744073709551629.0;
double res=a+b;
cout<<(res<mod?res:res-mod)<<endl;

Не получится. ~~double тоже имеет размер 64 бита.~~ Кое-где long double может иметь больший размер (обычно 80). Но даже если long double будет иметь размер в 128 бит, то под мантиссу пойдет только часть из них, и при значении a, скажем, 2^63 + 2^10 + 1 мы даже теоретически не сможем получить точного результата, не говоря уж о том, что числа с плавающей точкой работают иначе, чем целые.

@nmcf · 14.12.2014, 18:46

Посмотрел описание. Арифметика целочисленная, mod - остаток от деления.
Там нужны целые 128 бит. Стандартными средствами не решить, нужно искать какую-то библиотеку.

@Somebody · 14.12.2014, 18:48

Даже если long double будет на x86 80-битный, у него мантисса 64 бита - маловато. Так что тут полудлинная арифметика.

Байт · 14.12.2014, 19:03

C++
1
2
3
4
5
6
7
unsigned long a1, a2, b; // или другой 64-битный целый тип, поддерживаемый твоим компилятором
b = a1 + a2;
if (b >= a1) printf("%lu", b);
else {
 if (b < 13) printf("2^64 +%lu", b);
 else printf("%lu", b-13);
}

@nmcf · 14.12.2014, 19:28

Байт, а где умножение?

Байт · 14.12.2014, 20:39

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

Байт, а где умножение?

А тебе зачем? Это уже за отдельные деньги

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

@nmcf · 14.12.2014, 20:41

Какие ещё деньги?

Я говорю, что в описании алгоритма предполагаются целые 128 бит, поэтому смысл твоего фрагмента с a1 + a2 мне не ясен.

Байт · 14.12.2014, 20:54

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

Какие ещё деньги?

Это шутка.

Понимаешь, шутка это

А доля шутки тут в том, что это уже другая задача.

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

предполагаются целые 128 бит,

Для 128 бит задача тривиальна и пуста. Идея ее в том, что модуль на границе (за границей) разрядной сетки.

Новые блоги и статьи Все статьи Все блоги /
Kubernetes с Apache Flink для обработки данных в реальном времени Mr. Docker 17.05.2025 Kubernetes — это целая философия управления распределёнными приложениями. В отличие от "примитивных" решений вроде Docker Swarm, K8s (как его ласково называют в тусовке DevOps-инженеров) предлагает. . .	Использование декораторов в Python py-thonny 17.05.2025 Если вы когда-нибудь задумывались о том, как красиво расширить функциональность кода без лишней возни и дублирования, декораторы в Python — та самая волшебная палочка, которую вы искали. По сути, это. . .	Как некоторые отстают в навыках поиска информации в сети. Дублирование страницы открытого адреса в сети. Hrethgir 17.05.2025 . . . берём бразуер, для многих он является инструментом поиска информации в сети. Понятное дело, что чтобы переходить по сслыкам есть такая фишка - "открыть в новой вкладке", но, представим себе что вы. . .	Реализация многопоточных сетевых серверов на Python py-thonny 16.05.2025 Когда сталкиваешься с необходимостью писать высоконагруженные сетевые сервисы, выбор технологии имеет критическое значение. Python, со своей элегантностью и высоким уровнем абстракции, может. . .	C# и IoT: разработка Edge приложений с .NET и Azure IoT UnmanagedCoder 16.05.2025 Мир меняется прямо на наших глазах, и интернет вещей (IoT) — один из главных катализаторов этих перемен. Если всего десять лет назад концепция "умных" устройств вызывала скептические улыбки, то. . .
Гибридные квантово-классические вычисления: Примеры оптимизации EggHead 16.05.2025 Гибридные квантово-классические вычисления — это настоящий прорыв в подходах к решению сложнейших вычислительных задач. Представьте себе союз двух разных миров: классические компьютеры, с их. . .	Использование вебсокетов в приложениях Java с Netty Javaican 16.05.2025 HTTP, краеугольный камень интернета, изначально был спроектирован для передачи гипертекста с минимальной интерактивностью. Его главный недостаток в контексте современных приложений — это. . .	Реализация операторов Kubernetes Mr. Docker 16.05.2025 Концепция операторов Kubernetes зародилась в недрах компании CoreOS (позже купленной Red Hat), когда команда инженеров искала способ автоматизировать управление распределёнными базами данных в. . .	Отражение в C# и динамическое управление типами stackOverflow 16.05.2025 Reflection API в . NET — это набор классов и интерфейсов в пространстве имён System. Reflection, который позволяет исследовать и манипулировать типами, методами, свойствами и другими элементами. . .	Настройка гиперпараметров с помощью Grid Search и Random Search в Python AI_Generated 15.05.2025 В машинном обучении существует фундаментальное разделение между параметрами и гиперпараметрами моделей. Если параметры – это те величины, которые алгоритм "изучает" непосредственно из данных (веса. . .

@rudeeeboy 14 / 14 / 4 Регистрация: 08.11.2010 Сообщений: 172

	Как выполнить сложение по модулю 2^64+13 14.12.2014, 15:31. Показов 5836. Ответов 19 Метки нет (Все метки) Всем привет, есть два 64 битовых числа, как можно сделать сложение по модулю mod(2^64+13)? 0

@nmcf 7803 / 6567 / 2988 Регистрация: 14.04.2014 Сообщений: 28,705
	14.12.2014, 15:34
	По какому модулю? 0

@rudeeeboy 14 / 14 / 4 Регистрация: 08.11.2010 Сообщений: 172
	14.12.2014, 15:37 [ТС]
	вот полное выражение x=(((a*m+b)mod(2^64+13))mod(2^64) 0

@nmcf 7803 / 6567 / 2988 Регистрация: 14.04.2014 Сообщений: 28,705
	14.12.2014, 15:41
	Я говорю, mod - это что за функция? И что такое ^ в твоей записи? 0

@rudeeeboy 14 / 14 / 4 Регистрация: 08.11.2010 Сообщений: 172
	14.12.2014, 15:44 [ТС]
	mod - модуль ^ - степень 0

@AleksRazgul 35 / 17 / 10 Регистрация: 13.12.2014 Сообщений: 107
	14.12.2014, 16:08
	nmcf Я сомневаюсь что такой вариант прокатит. Мне кажется что в результате получится 0, если компилятор будет использовать 32-x битное или 64-x битное значение. То что он будет использовать 128-ми битное значение я сомневаюсь. Добавлено через 6 минут для возведения в степень лучше использовать pow(значение, степень) 0

@gunslinger place status here 3180 / 2208 / 640 Регистрация: 20.07.2013 Сообщений: 5,896
	14.12.2014, 16:11
	mod здесь скорей всего остаток от деления, пусть и называется модулем. 0

@rudeeeboy 14 / 14 / 4 Регистрация: 08.11.2010 Сообщений: 172
	14.12.2014, 16:32 [ТС]
	так что делать тогда с mod(2^64+13)? я пытаюсь реализовать этот алгоритм https://ru.wikipedia.org/wiki/DFC 0

@nmcf 7803 / 6567 / 2988 Регистрация: 14.04.2014 Сообщений: 28,705
	14.12.2014, 17:37
	Ну я подумал, что здесь целочисленная арифметика. Если нет, то, разумеется, pow(). 0

@Гром 212 / 131 / 28 Регистрация: 20.03.2009 Сообщений: 1,123 Записей в блоге: 16
	14.12.2014, 18:19
	Самый простой и наглядный способ - использовать длинную арифметику (гуглим "длинная арифметика"). Возможно, существуют способы получить результат, использую 32- или 64-битные целые, но они, вероятно, будут гораздо более сложными для понимания и/или реализации. 1

@nmcf 7803 / 6567 / 2988 Регистрация: 14.04.2014 Сообщений: 28,705
	14.12.2014, 18:46
	Посмотрел описание. Арифметика целочисленная, mod - остаток от деления. Там нужны целые 128 бит. Стандартными средствами не решить, нужно искать какую-то библиотеку. 0

@Somebody 2838 / 1647 / 254 Регистрация: 03.12.2007 Сообщений: 4,222
	14.12.2014, 18:48
	Даже если long double будет на x86 80-битный, у него мантисса 64 бита - маловато. Так что тут полудлинная арифметика. 0

@nmcf 7803 / 6567 / 2988 Регистрация: 14.04.2014 Сообщений: 28,705
	14.12.2014, 19:28
	Байт, а где умножение? 0

@nmcf 7803 / 6567 / 2988 Регистрация: 14.04.2014 Сообщений: 28,705
	14.12.2014, 20:41
	Какие ещё деньги? Я говорю, что в описании алгоритма предполагаются целые 128 бит, поэтому смысл твоего фрагмента с a1 + a2 мне не ясен. 0