Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Алгоритмы > Найти ближайшее квадратичное число


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

Автор: nostromo 19.4.2006, 16:29
Пусть [x] --- целая часть числа x, тогда

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

Автор: SoWa 20.4.2006, 11:15
Возможен перебор типа:
Код

for i:=x downto 0 do
begin
if trunc(sqrt(i))=sqrt(i) then 
 Г=sqrt(i)
 E=i 
end;
 

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

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

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

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

Автор: nostromo 20.4.2006, 14:38
Согласен.

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

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

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

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

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

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

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

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

Автор: MBo 24.4.2006, 09:50
Код

var
  N, Q, QSqrt, Rem: Integer;
begin
  N := 31;
  Rem := -N;
  QSqrt := -1;
  while Rem < 0 do begin
    Inc(QSqrt, 2);
    Inc(Rem, QSqrt);
  end;
  QSqrt := QSqrt div 2;
  Q := QSqrt * QSqrt;
  if N - Q < Rem then
    Rem := N - Q
  else begin
    Q := N + Rem;
    Inc(QSqrt)
  end;
  Caption := Format('N: %d  корень: %d  квадрат: %d  отклонение: %d',
    [N, QSqrt, Q, Rem]);

 

Автор: nostromo 24.4.2006, 11:19
???

Может, так:
Код

var
  N, Q, QSqrt, q1, q2, Rem: Integer;
begin
  N := 31;
  QSqrt := trunc(sqrt(N));
  q1 := QSqrt * QSqrt;
  q2 := (QSqrt+1) * (QSqrt+1);
  if (N-q1) > (q2-N) then
      QSqrt := QSqrt + 1;
  end;
  Q := QSqrt * QSqrt;
  Rem := abs(N - Q);
  Caption := Format('N: %d  корень: %d  квадрат: %d  отклонение: %d',
    [N, QSqrt, Q, Rem]);
 

Автор: MBo 24.4.2006, 12:52
nostromo

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

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

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

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

Автор: MBo 24.4.2006, 13:47
>Вы его тестировали?
Ну да. Вот пример выдачи:

Код

procedure TForm10.Button4Click(Sender: TObject);
var
  i, N, Q, QSqrt, Rem: Integer;

  procedure GetNums(N: Integer; var Q, QSqrt, Rem: Integer);
  begin
    Rem := -N;
    QSqrt := -1;
    while Rem < 0 do begin
      Inc(QSqrt, 2);
      Inc(Rem, QSqrt);
    end;
    QSqrt := QSqrt div 2;
    Q := QSqrt * QSqrt;
    if N - Q < Rem then
      Rem := N - Q
    else begin
      Q := N + Rem;
      Inc(QSqrt)
    end;
  end;

begin
  Randomize;
  Memo1.Lines.Clear;
  for i := 0 to 10 do begin
    N := 1 + Random(100);
    GetNums(N, Q, QSqrt, Rem);
    Memo1.Lines.Add(Format('%3d  =  %d  (%d*%d)   +-   %d',    [N, Q, QSqrt, QSqrt, Rem]));
  end;
end;


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

 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 

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

Автор: tishaishii 24.4.2006, 14:11
Да, я в формуле ошибся.

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] 

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

Код

  procedure GetNums2(N: Integer; var Q, QSqrt, Rem: Integer);
  var
    OneOne, i : Integer;
  begin
    OneOne := $40000000;
    QSqrt := 0;
    Rem := N;
    for i := 0 to 15 do begin
      if Rem >= OneOne + QSqrt then begin
        Dec(Rem, OneOne + QSqrt);
        QSqrt := (QSqrt shr 1) or OneOne;
      end else
        QSqrt := QSqrt shr 1;
      OneOne := OneOne shr 2;
    end;
    Q := N - Rem;
    if Rem > QSqrt then begin
      Q := Q + (QSqrt shl 1) + 1;
      Inc(QSqrt);
      Rem := N - Q;
    end;
  end;

 

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

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

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

Автор: nostromo 24.4.2006, 16:35
Цитата

Вообще, как он в Delphi работает, этот div? Я думаю, подбором.


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

Автор: tishaishii 24.4.2006, 16:35
n - это система счисления такая.

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

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

Добавлено @ 16:38 
Цитата(nostromo @ 24.4.2006,  16:35)
Цитата

Вообще, как он в Delphi работает, этот div? Я думаю, подбором.


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

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

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

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

Два такта никак занять не сможет, если div работает как и деление / ...

Сейчас уточнил. Не пару тактов, но довольно мало:
http://mcs.uwsuper.edu/sb/324/Intro/mulcyc.html  

Автор: nostromo 24.4.2006, 17:07
Цитата

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


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

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

Автор: tishaishii 24.4.2006, 23:37
Ну так вопрос открыт. 

Автор: Маг 5.7.2006, 11:14
 smile И над какими задачами еще потешаешся????

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

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)