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

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

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

Всем привет, есть два 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 бит задача тривиальна и пуста. Идея ее в том, что модуль на границе (за границей) разрядной сетки.

Новые блоги и статьи Все статьи Все блоги /
Символьное дифференцирование igorrr37 13.02.2026 / * Логарифм записывается как: (x-2)log(x^2+2) - означает логарифм (x^2+2) по основанию (x-2). Унарный минус обозначается как ! */ #include <iostream> #include <stack> #include <cctype>. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .

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

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

@nmcf 7804 / 6568 / 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 7804 / 6568 / 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 3186 / 2220 / 640 Регистрация: 20.07.2013 Сообщений: 6,013
	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 7804 / 6568 / 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 7804 / 6568 / 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 7804 / 6568 / 2988 Регистрация: 14.04.2014 Сообщений: 28,705
	14.12.2014, 19:28
	Байт, а где умножение? 0

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