Длинная арифметика. С (С++)

[whitefox]

Xaositect в сообщении #835756 писал(а):

Это неприятная штука, тестами может не ловиться. Ошибка возникнет, если старое число на границе выделенной страницы памяти и элемент с чужой страницы система прочитать не даст.

Почему тогда следующая программа работает?

Используется синтаксис C++

#include <iostream>

using namespace std;

int main(){       
     const int pagesize = 0x1000;
     unsigned char* p = new unsigned char;
     cout << hex << uppercase << (unsigned)p << ": ";    
     for(int i = 0; i <= pagesize; i++) cout << (unsigned)p[i] << ' ';
     cout << endl;
}

[Xaositect]

У меня размер страницы 4096 и похожая программа стабильно дает сегфолт на 135151 байте, и я не знаю точно, почему именно это число. Оно при этом зависит от того, включена ли оптимизация в компиляторе, возможно, зависит от размера программы.
Возможно, кто-нибудь более знакомый с устройством управления памятью в какой-нибудь ОС сможет ответить.

[vlad_light]

На всякий случай напишу тест-код:

#include <string.h>
 
#define size 1024
int x[size] __attribute__((aligned(4096))) = { 0 };
 
int main (void)
{
  int y[size + 1];
  memcpy(y, x, (size + 1) * sizeof(int));
  y[size] = 0;
  return 0;
}

Эта программа по идее должна падать. Если вдруг она не падает -- это скорее всего из-за того, что в библиотеке, с которой статически линкуется программа, есть глобальные данные и они буду находиться правее от $x$. Следовательно, выход за границу попадет на библиотечные переменные. Всё это нужно запускать в режиме Release.

[Joker_vD]

Еще раз напоминаю всем, кому было лень прочитать нормальную книжку по Си или C++: чтение по невыделенному адресу — это undefined behaviour. Произойти может что угодно: программа может увидеть там ноль, или что-то еще, может упасть, может выложить все ваши пароли на Google Docs в открытый доступ, может отформатировать ваш жесткий диск. И нет, последние две возможности — вовсе не ради красного словца.

"Почему следующая программа работает?" Почему бы и нет, это ей не запрещено. "Почему она падает на 135151-м байте?" Почему бы и нет, это ей не запрещено. "Это программа по идее должна падать" — нет, она ничего вам не должна. Абсолютно. Разыменование нулевого указателя не обязано приводить к падению — и бывают случаи когда они не приводят.

MyClass z;
MyClass& a = *nullptr;
*((MyClass**)(&a)) = ((MyClass*)(a) + (&z - nullptr));
a.some_method();

или как-то так — имеет все шансы вызвать z.some_method(), не упав.

[vlad_light]

(Оффтоп)

Joker_vD в сообщении #836354 писал(а):

нет, она ничего вам не должна.

Простите, но я же не зря написал "по идее". И даже объяснил возможную причину "правильности" выполнения:

vlad_light в сообщении #836316 писал(а):

это скорее всего из-за того, что в библиотеке, с которой статически линкуется программа, есть глобальные данные и они буду находиться правее от $x$. Следовательно, выход за границу попадет на библиотечные переменные. Всё это нужно запускать в режиме Release.

Причем, хочу заметить, что тут я также употребил фразу "скорее всего".
В остальном -- полностью согласен.

По квадрату подсказки есть?

[whitefox]

Joker_vD в сообщении #836354 писал(а):

Еще раз напоминаю всем, кому было лень прочитать нормальную книжку по Си или C++:

А причём здесь С/С++ ?
Программа может быть написана и на ассемблере.
Вопрос состоял в том: в каких случаях ОС запретит доступ по невыделенному адресу на соседней виртуальной странице?

[vlad_light]

Joker_vD имел ввиду, что всё, что не описано по стандарту -- делать нельзя; и воспринимать это нужно как аксиому. Т.е. неопределенное поведение не нуждается в объяснении.

whitefox в сообщении #836368 писал(а):

А причём здесь С/С++ ?

Скорее всего при том, что я писал выкладки на этих языках.

whitefox в сообщении #836368 писал(а):

в каких случаях ОС запретит доступ по невыделенному адресу на соседней виртуальной странице?

Скорее всего на этот вопрос нет однозначного ответа. Свои мысли по этому поводу (с примером) я уже написал. Передаю слово более опытным специалистам.

[whitefox]

vlad_light
Согласен с Вами, в данной теме мой вопрос является оффтопиком.
Поэтому я его снимаю.

[vlad_light]

Joker_vD в сообщении #836072 писал(а):

vlad_light в сообщении #835995 писал(а):

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

Бенчмарк в студию? http://stackoverflow.com/a/16446991/1440433 показывает обратное.

Неправильно замерял. Прошу прощения и беру свои слова назад (если можно ).

[vlad_light]

Друзья, помогите, пожалуйста, с делением.
Пусть имеются $n, p\in \mathbb N$, нужно найти $q, r\in \mathbb N$ такие, что $n=pq+r$.
Я выбрал метод Ньютона с функцией $f(x)=\frac {1}{xp}-1$, где $ f(\frac 1p) \approx 0$. Тогда $\lfloor n\cdot \frac 1p \rfloor =q$
Сразу вопрос: можно ли таким же методом найти $r$, не находя $q$?
Итерации будут иметь вид: $x_{i+1}=x_i (2-px_i)$. Поскольку у меня числи целые, я буду представлять $x_n$ в виде рационально дроби со знаменателем $b^m, m\in\mathbb N$, где $b$ -- основание системы счисления (в моём случае $b=2^{32}$).
Как оценить $x_0$? Я придумал оценку $x_0=\frac {1}{b^{\lceil \log _b p\rceil}}$. Плюсы этой оценки в её простоте, минусы -- во всем остальном Другие оценки, над которыми я думал: пусть $\mathbb P_k(p)=\sum _{i = 0}^kc_ip^i$. Ограничим $p\in [a, b]$, тогда $\|\frac {1}{p}-\mathbb P_k \|_{L^\alpha(a, b)}\to \min$, где $\alpha= 2, \infty$. Во всех оценках нужно оценить необходимое кол-во итераций. Причем, при $\alpha = 2$ можно сделать определенное кол-во итераций, а затем пока не выполнится $|x_{i+1}-x_i|<\varepsilon$.
Следовательно, вопрос: как оценить кол-во итераций для каждого случая?
Поскольку с каждой итерацией у нас очень быстро растёт кол-во цифр в $x_i$, их необходимо урезать (брать только несколько значущих -- остальные выкидывать).
Как оценить кол-во цифр, которые можно урезать?
Заранее всем благодарен за любые подсказки!

[Joker_vD]

https://gmplib.org/~tege/division-paper.pdf

[Xaositect]

vlad_light в сообщении #839350 писал(а):

Как оценить $x_0$?

vlad_light в сообщении #839350 писал(а):

как оценить кол-во итераций для каждого случая?

Метод Ньютона сходится квадратично, то есть количество верных знаков каждый раз удваивается. Ваша оценка хорошая, обычно она и используется.
Более точно, если $1 - 2^{-m} \leqslant x_n p \leqslant 1+ 2^{-m}$, то для $x_{n + 1} = x_n(2 - px_n)$ выполняется $1 - 2^{-2m}\leqslant x_{n+1}p \leqslant 1$