Факторизация Ферма в C++

Ради интереса я реализовал кое-какие математические штуки на C++ и пытался реализовать Fermats. Метод факторизации, однако я не знаю, понимаю ли я, что он должен возвращать. Эта реализация, которая у меня есть, возвращает 105 для номера примера 5959, указанного в статье Википедии.

Псевдокод в Википедии выглядит так:

Пробуют разные значения a, надеясь, что это квадрат.

FermatFactor(N): // N should be odd
    a → ceil(sqrt(N))
    b2 → a*a - N
    while b2 isn't a square:
        a → a + 1    // equivalently: b2 → b2 + 2*a + 1
        b2 → a*a - N //               a → a + 1
    endwhile
    return a - sqrt(b2) // or a + sqrt(b2)

Моя реализация на С++ выглядит так:

int FermatFactor(int oddNumber)
{
    double a = ceil(sqrt(static_cast<double>(oddNumber)));
    double b2 = a*a - oddNumber;
    std::cout << "B2: " << b2 << "a: " << a << std::endl;

    double tmp = sqrt(b2);
    tmp = round(tmp,1);
    while (compare_doubles(tmp*tmp, b2))  //does this line look correct?
    {
        a = a + 1;
        b2 = a*a - oddNumber;
        std::cout << "B2: " << b2 << "a: " << a << std::endl;
        tmp = sqrt(b2);
        tmp = round(tmp,1);
    }

    return static_cast<int>(a + sqrt(b2));
}

bool compare_doubles(double a, double b)
{
    int diff = std::fabs(a - b);
    return diff < std::numeric_limits<double>::epsilon();
}

Что он должен вернуть? Кажется, просто возвращается a + b, что не является фактором 5959?

ИЗМЕНИТЬ

double cint(double x){
    double tmp = 0.0;
    if (modf(x,&tmp)>=.5)
        return x>=0?ceil(x):floor(x);
    else
        return x<0?ceil(x):floor(x);
}

double round(double r,unsigned places){
    double off=pow(10,static_cast<double>(places));
    return cint(r*off)/off;
}

person Tony The Lion    schedule 06.05.2012    source источник
comment
static_cast<double>(b2)? Там есть причина? Также как определяется compare_doubles?   -  person jli    schedule 07.05.2012
comment
@jli b2 был int в моей предыдущей реализации, позвольте мне изменить его, у него больше нет причин для существования   -  person Tony The Lion    schedule 07.05.2012
comment
Я бы использовал целые типы для tmp и b2. Чтобы тесты прошли, вам в любом случае нужен целочисленный квадратный корень из b2. На самом деле реализация с целыми числами для всех локальных переменных возвращает 101. :)   -  person vhallac    schedule 07.05.2012
comment
Что это за функция раунда с двумя аргументами?   -  person Mat    schedule 07.05.2012


Ответы (3)


Обратите внимание, что вы должны выполнять все эти вычисления для целочисленных типов, а не для типов с плавающей запятой. Это было бы намного проще (и, возможно, правильнее).


Ваша функция compare_doubles неверна. diff должно быть double.

И как только вы это исправите, вам нужно будет исправить свою тестовую строку. compare_doubles вернет true, если его входы «почти равны». Вам нужно зацикливаться, пока они «почти не равны».

So:

bool compare_doubles(double a, double b)
{
    double diff = std::fabs(a - b);
    return diff < std::numeric_limits<double>::epsilon();
}

А также:

while (!compare_doubles(tmp*tmp, b2))  // now it is
{

И вы получите правильный результат (101) для этого ввода.

Вам также нужно будет вызвать функцию round с 0 как "места", как указывает vhallac - вы не должны округление до одного знака после запятой.

В статье Википедии, на которую вы ссылаетесь, есть уравнение, которое позволяет вам идентифицировать b из N и a-b.

person Community    schedule 06.05.2012
comment
Хех, я пропустил ошибку int diff. :) - person vhallac; 07.05.2012
comment
Добавил ссылку, сделал CW для коллективных усилий ;-) - person Mat; 07.05.2012

В вашем коде две проблемы:

  1. compare_doubles возвращают true, когда они достаточно близки. Таким образом, условие цикла while инвертируется.
  2. Функция round требует количества цифр после запятой. Поэтому вы должны использовать round(x, 0).

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

person vhallac    schedule 06.05.2012
comment
Блин, пропустил круглый баг :) - person Mat; 07.05.2012
comment
:) Ваш ответ более полный. Не стесняйтесь добавлять это к своему, чтобы его можно было выбрать как правильный. - person vhallac; 07.05.2012

Два фактора: (a+b) и (a-b). Он возвращает один из них. Вы можете легко получить другой.

N = (a+b)*(a-b)
a-b = N/(a+b)
person Vaughn Cato    schedule 06.05.2012
comment
Как я должен легко получить другого от a + b ?? - person Tony The Lion; 07.05.2012