Надо быстро найти ближайшее квадратичное число и остаток.
Например, дано целое неотрицательное число Б=27, надо найти число В=25, число Г=5 и число Е=2
Итого: Б=Г^2+Е=В+Е. 

Пусть [x] --- целая часть числа x, тогда

Г = [sqrt(Б)],
E = Б - Г^2.
 

Возможен перебор типа:
 

Что-то не то вы написали, уважаемый SoWa.
В результате выполнения вашего цикла в перменных Г и Е окажется 0 независимо от x.    

Ничего подобного, идет проверка, когда корень будет целым числом. Вот и все. Твое решение конечно лучше, но я предложил просто другой способ. 

Ну во-первых --- это не откомпилируется (кажется, это Паскаль), а во-вторых, на последней инерации цикла при i=0 условие всегда сработает.
 

nostromo, в твоем алгоритме стоит еще проверить какое число ближе к x: [sqrt(Б)]^2 или ([sqrt(Б)]+1)^2
Если Б=35, то по твоему алгоритму Г=5, хотя ближайшее квадратичное число B=36, а не 25. 

Согласен.

Г1 := [sqrt(Б)].
Г2 := Г1 +1.

... бла-бла-бла
 

Ну какой-то способ вы предлагаете совсем не быстрый. Мне он не подойдёт. Нахождение корня, деление и т.д. - это же очень долго.
Может быть, мои рассуждения помогут.

x[i+2]=x[i+1]-x[i]+2

Где x - квадратичное число.
Но я пока задачу не решил. 

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

Добавлено @ 09:39 
Рассуждения не понял:
25 = 16 - 9 + 2 ???
В чем идея?

Может, нужно найти "квадратичные" числа сразу для ряда чисел? 

 

???

Может, так:
 

nostromo

Я привел метод без использования Sqrt, округления и вообще без вещественной арифметики, раз уж автору это интересно.
Конечно, для больших чисел выгоднее корень извлечь.
 

Виноват. Мне показалось, что это не Вы, а автор темы привел кусок неработающего кода.

У меня нет под руками Паскаля, но, клянусь своей треуголкой, Ваш код, MBo, не может в принципе работать правильно.
Вы его тестировали? Что если поставить N=100?
 

для целых чисел можно попробовать метод бисекции - для 32-битного числа достаточно будет сделать шагов 17, да и операции там простые... 

>Вы его тестировали?
Ну да. Вот пример выдачи:



+-  - т.к. вычисляется модуль отклонения

 19  =  16  (4*4)   +-   3
 71  =  64  (8*8)   +-   7
 99  =  100  (10*10)   +-   1
 60  =  64  (8*8)   +-   4
 53  =  49  (7*7)   +-   4
 96  =  100  (10*10)   +-   4
100  =  100  (10*10)   +-   0
 82  =  81  (9*9)   +-   1
 97  =  100  (10*10)   +-   3
 58  =  64  (8*8)   +-   6
 53  =  49  (7*7)   +-   4 

Да, сумма последовательных нечетных пробегает все квадраты. Каюсь, не разглядел.  

Да, я в формуле ошибся.

0, 1
1*2-0+2=4
4*2-1+2=9
9*2-4+2=16
16*2-9+2=25
..........
и так далее всё правда.

X[i-1]*2-X[i-2]+2=X[i] 

tishaishii, ты скажи, для чего это нужно, а то вот еще целочисленный алгоритм с 16 оборотами цикла (а не Sqrt(N))   


 

А можно что-нибудь с вышеприведённой формулой замутить?
Мне кажется, что для моей задачи div использовать противопоказано.
Вообще, как он в Delphi работает, этот div? Я думаю, подбором.

Да, уточню. Мне надо найти ближайшее квадратичное число, которое не больше данного (т.е. остаток всегда положительный).

Ну вот ещё одна формула: (k(n)^(2*m)) mod (n-1)=0, я думаю, она тоже имеет прямое отношение к этой задаче. 

Скорее всего вчисления div займет 2 такта процессора (советую познакомиться с его базовым набором команд). 

n - это система счисления такая.

MBo, ты не поверишь, мне это нужно как раз для того, о чём я уже рассказал в первом посте

Я буду работать с огромными числами (десятичная запись которых занимает мегабайты). Это вычисление - часть алгоритма.

Добавлено @ 16:38 

Ну как оно работает?
Два такта никак занять не сможет, если div работает как и деление /, т.к. деление / до сих пор происходит подбором. Интересно знать формулу div (именно ту, по которой действует процессор). 

P.S. В дельфи есть возможность просмотра дизассемблерного листинга и, скорее всего, можно найти профайлер.

Добавлено @ 16:54 

Сейчас уточнил. Не пару тактов, но довольно мало:
idiv  

Это сообщение отредактировал(а) nostromo - 24.4.2006, 16:54

Я знаю только одну возможную область применения таких вещей --- теория чисел и криптография, как ее приложение. Кстати, почему вы уцепились за перебор, ведь он по сути находит квадратный корень из числа (с точностью до 1), а от корня до квадратичного числа --- одно умножение? Замечу, что эффективный алгоритм извлечения квадратного корня связан с диофантовым уравнением Пелля. 
Не желаете рассказать о задаче поподробнее?     

Это сообщение отредактировал(а) nostromo - 24.4.2006, 17:08

Моя задача связана исключительно с потешанием над числами и прочей математикой.
За страницу - спасиба. 

Ну так вопрос открыт. 

  И над какими задачами еще потешаешся????

ПыСы как извлекать  быстро корень не раскажеш?А то не могу найти нормального алгоритма без всяких трудностей в реализации