Ошибка преобразования типа

@G@leON · Регистрация: 02.06.2009

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

Задача состояла в следующем: реализация алгоритма проверки n на простоту, используя малую теорему Ферма. В силу недостаточного опыта и позднего времени накумекал следующий код с пояснениями:

В качестве 1 из параметров, передаваемых функциям, выступает маркер простоты.
Это параметр-ссылка на переменную логического типа.
Значение маркера = true после выполнения подтверждает простоту проверяемого числа.

C++

int gcd(int v_1, int v_2){
    while (v_2){
        int temp = v_2;
        v_2 = v_1 % v_2;
        v_1 = temp;
    }
    return v_1;
}
 
void ferma_lt_test(bool &prime_marker, int n){
    prime_marker = true;
    if (n<1){
        prime_marker = false;
        cout << "n is not natural" << endl;
    }
    if (n>2) {
        int v_1 = 2;
        while ((gcd(n,v_1)) != 1)
            v_1++;
        double deg_v = n, base_v = v_1;
        long l_v1 = exp(deg_v * log(base_v)), l_v2 = exp((deg_v - 1) * log(base_v));
        l_v1 %= n;
        l_v2 %= n;
        if ((l_v1 != v_1) || (l_v2 != 1))
            prime_marker = false;
    }
}

Здесь ф-ция gcd(v_1,v_2) - нахождение НОД. Вторая функция: Тест малой теоремой Ферма.

Ошибка заключается собственно в том, что при преобразовании double в long в строке:

C++ (Qt)

1	long l_v1 = exp(deg_v * log(base_v)), l_v2 = exp((deg_v - 1) * log(base_v));

Оба значение типа long на 1 меньше, чем возвращаемые функциями значения типа double. Притом, данная ошибка вылезает для чисел до 19 включительно. Число 23, как ни странно, проверяется. Помогите исправить.

Соответственно, число 31 уже выходит за границу допустимого диапазона. Было бы неплохо, так же, услышать подсказку по увеличению допустимого диапазона (например, имеется ли стандартный модуль(заголовок) длинной математики в C++, а если нет, то какой лучше и где найти...).

Добавлено через 52 минуты
После проверки на различные варианты преобразования выяснил, что они не помогают, ни преобразование в стиле C, не преобразование в стиле С++ (cast которые). Конечно, проблему можно разрешить проверкой на принадлежность к определенному числу (типа if n < 19 ... то прибавлять к функции +1), но это вообще не выход. Так что проблему надо решать альтернативным методом. Каким, не знаю.

Я так понимаю, задача вылазит несколько другим боком. Нужно как то умудрится возвести в степень n и n-1 число v_1, а результат потом делить на n с получением остатка от деления.

@Toshkarik · 10.05.2012, 07:23

Не по теме:

Сообщение от G@leON

А ставить несколько спасибо можно?

За любое показавшееся Вам полезным сообщение.

Посмотрел функцию решета Эратосфена - можно свести к более простому варианту:

C++

vector< bool > vec( number );
fill( vec.begin(), vec.end(), true );
for ( size_t i = 2; i < vec.size(); i++ )
   if ( vec[ i ])
      for( size_t j = i + i; j < vec.size(); j += i )
         vec[ j ] = false;

@taras atavin · 10.05.2012, 07:25

Сообщение от Avazart

Может человек имеет ввиду округление, а не приведение типов?

А чем округление до целого отличается от приведения дроби к целому?

@Toshkarik · 10.05.2012, 07:28

Сообщение от taras atavin

А чем округление до целого отличается от приведения дроби к целому?

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

@taras atavin · 10.05.2012, 07:44

Сообщение от G@leON

Оба значение типа long на 1 меньше, чем возвращаемые функциями значения типа double.

А при чём здесь ошибка приведения? Ошибка приведения, это когда вообще нельзя привести. А здесь погрешность округления. Твой double чуть меньше ожидаемого целого.

C++

int x;
int y;
float z;
z=2.5;
x=z;// Округление вниз, x=2
y=z+0.5;// Округление по математическим правилам, y=3

Добавлено через 8 минут

Сообщение от Toshkarik

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

Существует как минимум 4 способа округления: вниз, вверх, по математическим правилам и так называемое банкирское, по правилам которого если дробная часть точно равна 0.5, то округляют к ближайшему чётному, а в остальных случаях к ближайшему целому, при округлении вниз дробная часть отбрасывается, при округлении вверх при ненулевой дробной части инкремируется целая, а при нулевой сохраняется и после этого отбрасывается дробная часть, а оператор приведения типа может быть написан как угодно и предусматривать какое нибудь вообще пятое округление. В любом случае обнуление младших разрядов в какой либо системе счисления есть округление (округлять можно и до сотен, и до сотых), а приведение к целому всегда обнуляет все разряды с весами меньше единицы, что есть округление до целого. То, что встроенные типы принято приводить именно округлением вниз, сути не меняет.

Добавлено через 6 минут

Сообщение от G@leON

Я так понимаю, задача вылазит несколько другим боком. Нужно как то умудрится возвести в степень n и n-1 число v_1, а результат потом делить на n с получением остатка от деления.

Если и основание, и показатель целые, то зачем возводить в степень через экспоненту? Для данного случая степень определена, как произведение одинаковых множителей, так и делай.

@Toshkarik · 10.05.2012, 07:46

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

Сообщение от taras atavin

написан как угодно

Не как угодно, отбрасывается именно дробная часть.

@taras atavin · 10.05.2012, 07:51

C++

long int degree(long int a, unsigned int n)// a в степени n
{
 int n1;
 if (n==1)
 {
  return a;
 }
 if (n==0)
 {
  return 1;
 }
 n1=n/2;
 return (degree(a, n1)*degree(a, n-n1)); 
}

, или

C++

long int degree(long int a, unsigned int n)// a в степени n
{
 int r;
 for (r=1; n>0; --n)
 {
  r*=a;
 }
 return r; 
}

Добавлено через 3 минуты

Сообщение от Toshkarik

Не как угодно, отбрасывается именно дробная часть.

Как угодно. Конкретный способ принят только для стандартных типов и является всего лишь вопросом выбора авторов стандарта. Для своих типов ты можешь сделать даже так: если дробная часть строго меньше 0.5, то вверх, иначе вниз. И это тоже будет округление. Или можешь сделать математическое округление до кратного трём.

@Toshkarik · 10.05.2012, 07:54

При чем тут не стандартные типы? Вы тут видите приведение не стандартных типов? Для стандартных типов точно указано, что получится в итоге, и это никак не связанно с округлением. Это форум С++, если Вы вдруг упустили это из виду.

@taras atavin · 10.05.2012, 08:03

Для стандартных был выбран один из способов округления, выбор закрепили. И всего делов. Приведение стандартного вещественного к целому, это округление вниз до целого, а не что то абсолютно новое.

@Toshkarik · 10.05.2012, 08:07

Я же считаю, что данный способ был выбран исходя из природы чисел. Целое на то и целое, что в нем нет дробной части, поэтому она отбрасывается, и это не округление.

@G@leON · 10.05.2012, 08:18 **[ТС]**

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

По поводу параметра ссылки, а какая разница, передаете вы через параметр-ссылку, или просто возвращаете значение? Если вопрос удобства, то мне удобней через параметр-ссылку (либо параметр-указатель). Мне так логика понятней кажется.

@taras atavin · 10.05.2012, 08:20

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

@Toshkarik · 10.05.2012, 08:23

taras atavin, пусть каждый останется при своем мнении. Я по другому смотрю на приведение типа в данном случае, и оно никак не вяжется с округлением.

@Avazart · 10.05.2012, 17:41

Не путайте округление к ближайшему целому (то к которому нас в школе учили) и округление к меньшему(то которое предусмотрено ф-цией floor(), и впринципе происходит при в данном случаее при приведении).

И дело не в не правильном приведении типов, а в незнании того к чему оно приводит....

http://ru.wikipedia.org/wiki/Округление

@taras atavin 4226 / 1795 / 211 Регистрация: 24.11.2009 Сообщений: 27,562
	10.05.2012, 07:25	22
	Сообщение от Avazart Может человек имеет ввиду округление, а не приведение типов? А чем округление до целого отличается от приведения дроби к целому? 0

@Toshkarik 1181 / 894 / 94 Регистрация: 03.08.2011 Сообщений: 2,461
	10.05.2012, 07:54	27
	При чем тут не стандартные типы? Вы тут видите приведение не стандартных типов? Для стандартных типов точно указано, что получится в итоге, и это никак не связанно с округлением. Это форум С++, если Вы вдруг упустили это из виду. 0

@Toshkarik 1181 / 894 / 94 Регистрация: 03.08.2011 Сообщений: 2,461
	10.05.2012, 08:07	29
	Я же считаю, что данный способ был выбран исходя из природы чисел. Целое на то и целое, что в нем нет дробной части, поэтому она отбрасывается, и это не округление. 0

@G@leON 6 / 6 / 2 Регистрация: 02.06.2009 Сообщений: 99
	10.05.2012, 08:18 [ТС]	30
	За решето спасибо, удобный способ, по поводу приведения типов, это именно ошибка приведения, просто это не ошибка синтаксиса, а ошибка компиляции некрасивой логики. И да, именно с округлением она и связана, так что в формулировке не вижу повода сомневаться. По поводу параметра ссылки, а какая разница, передаете вы через параметр-ссылку, или просто возвращаете значение? Если вопрос удобства, то мне удобней через параметр-ссылку (либо параметр-указатель). Мне так логика понятней кажется. 0

@Toshkarik 1181 / 894 / 94 Регистрация: 03.08.2011 Сообщений: 2,461
	10.05.2012, 08:23	32
	taras atavin, пусть каждый останется при своем мнении. Я по другому смотрю на приведение типа в данном случае, и оно никак не вяжется с округлением. 0

@Toshkarik 1181 / 894 / 94 Регистрация: 03.08.2011 Сообщений: 2,461
	10.05.2012, 07:28	23
	Сообщение от taras atavin А чем округление до целого отличается от приведения дроби к целому? Тем, что при округлении берется ближайшее целое, при приведении же просто отбрасывается дробная часть. 0

@Toshkarik 1181 / 894 / 94 Регистрация: 03.08.2011 Сообщений: 2,461
	10.05.2012, 07:46	25
	Думаю, тут уместно обсуждение математического округления а не каких то там "банкирских" и тд. Приведение типа, как я считаю, никак не связанно с округлением. Сообщение от taras atavin написан как угодно Не как угодно, отбрасывается именно дробная часть. 0

@taras atavin 4226 / 1795 / 211 Регистрация: 24.11.2009 Сообщений: 27,562
	10.05.2012, 08:03	28
	Для стандартных был выбран один из способов округления, выбор закрепили. И всего делов. Приведение стандартного вещественного к целому, это округление вниз до целого, а не что то абсолютно новое. 0

@taras atavin 4226 / 1795 / 211 Регистрация: 24.11.2009 Сообщений: 27,562
	10.05.2012, 08:20	31
	Это именно округление. Отбрасывание дробной части есть округление вниз. А по какому принципу выбирали - вторично. Мне кажется, что выбрали вниз потому, что так проще. Но мотив выбора реализации не имеет ни какого отношения к наименованию операции. 0

@Avazart 8385 / 6147 / 615 Регистрация: 10.12.2010 Сообщений: 28,683 Записей в блоге: 30
	10.05.2012, 17:41	33
	Не путайте округление к ближайшему целому (то к которому нас в школе учили) и округление к меньшему(то которое предусмотрено ф-цией floor(), и впринципе происходит при в данном случаее при приведении). И дело не в не правильном приведении типов, а в незнании того к чему оно приводит.... http://ru.wikipedia.org/wiki/Округление 0