Здравствуйте!
Помогите пожалуйста решить задачу: нужно преобразовать число типа System.Double в обыкновенную дробь, т.е. найти числитель и знаменатель этой дроби (они имеют тип System.Numerics.BigInteger).
У меня есть только такая мысль:
1) выделить целую часть и записать её во временной переменной типа System.Numerics.BigInteger;
2) дробную часть умножить на 10^38 (значок ^ обозначает возведение в степень) и записать полученное значение в числитель;
3) знаменателю присвоить значение 10^38;
4) сократить полученную дробь;
5) временную переменную умножить на знаменатель, потом прибавить числитель и результат записать в числитель.
Мне кажется, что можно сделать более рационально.
Re: Преобразовать System.Double в обыкновенную дробь
Здравствуйте, Mak_71_rus, Вы писали:
M__>Мне кажется, что можно сделать более рационально.
Хз, я бы сделал так:
Зашёл бы сюда
Скачал бы оттуда zip-архивчик
Спёр бы из него cs-файлик
Подключил бы System.Numerics из BCL 4.0
Написал бы:
var x = 1.2345;
var n = new Numerics.BigRational(x);
Console.WriteLine("n = {0}", n);
Получил бы:
n = 5559693739988877/117813617286336735328947744983549524942387739291963003550715137987531686415893111198651827698013002
806801277832312516350875264462890216077716912492143885762152213966634919844430677422637872640242124772443478429380665770
43117995647400274369612403653814737339068225047641453182709824206687753689912418253153056587776
Катался бы
Re[2]: Преобразовать System.Double в обыкновенную дробь
Здравствуйте, Пельмешко, Вы писали:
П>Здравствуйте, Mak_71_rus, Вы писали:
M__>>Мне кажется, что можно сделать более рационально.
П>Хз, я бы сделал так:
Здравствуйте, Mak_71_rus, Вы писали:
M__>Помогите пожалуйста решить задачу: нужно преобразовать число типа System.Double в обыкновенную дробь, т.е. найти числитель и знаменатель этой дроби (они имеют тип System.Numerics.BigInteger).
Вероятно я чего-то не понимаю, но десятичную дробь всегда можно преобразовать в обыкновенную, разве нет?
ну например 1.234 будет 1234/1000. Можно начать сокращать, но это уже обыкновенная дробь и в принципе для условия задачи этого хватает.
Соот-но и алгоритм элементарный — надо только посчитать количество знаков после нуля. Сделать это можно конвертнув в строку и найдя точку, либо умножая на десять пока dbl != (int)dbl. Может ещё как-то, но это просто навскидку.
Сложность я вижу только в том, что double он неточный и в связи с этим разные косяки будут возникать. Но это уже другой вопрос, кажется.
всю ночь не ем, весь день не сплю — устаю
Re[2]: Преобразовать System.Double в обыкновенную дробь
Здравствуйте, Neco, Вы писали:
N>Здравствуйте, Mak_71_rus, Вы писали:
M__>>Помогите пожалуйста решить задачу: нужно преобразовать число типа System.Double в обыкновенную дробь, т.е. найти числитель и знаменатель этой дроби (они имеют тип System.Numerics.BigInteger). N>Вероятно я чего-то не понимаю, но десятичную дробь всегда можно преобразовать в обыкновенную, разве нет? N>ну например 1.234 будет 1234/1000. Можно начать сокращать, но это уже обыкновенная дробь и в принципе для условия задачи этого хватает. N>Соот-но и алгоритм элементарный — надо только посчитать количество знаков после нуля. Сделать это можно конвертнув в строку и найдя точку, либо умножая на десять пока dbl != (int)dbl. Может ещё как-то, но это просто навскидку. N>Сложность я вижу только в том, что double он неточный и в связи с этим разные косяки будут возникать. Но это уже другой вопрос, кажется.
Ну а если это 1,237684534567*10^-308 ? Просто умножение на 10^308 длится долго, вот я думаю как бы эффективнее выполнить преобразование.
Re[2]: Преобразовать System.Double в обыкновенную дробь
Здравствуйте, bornkiller, Вы писали:
B>Что-то приведенное число не выглядит большим единицы
А слона то я и не заметил...
Однако и глючные либы выкладывают ребята из BCL:
var a = new Numerics.BigRational(0.5D);
var b = new Numerics.BigRational(0.5M);
Console.WriteLine("a = {0}", a);
Console.WriteLine("a = {0}D", (double)a);
Console.WriteLine("a = {0}M", (decimal) a);
Console.WriteLine("b = {0}", b);
Console.WriteLine("b = {0}D", (double)b);
Console.WriteLine("b = {0}M", (decimal)b);
Результат:
a = 1/2743062034396844341627968125593604635037196317966166035056000994228098690879836473582587849768
1813968066423626689360558724790919313723239516120518591228351498072493503550031322677950988959670123
2075627063117989759579697696445408449514637925019572810613022629828775479492107003690307184303032465
1025760256
a = 3,6455610097782E-304D
a = 0M
b = 1/2
b = 0,5D
b = 0,5M
То есть импорт из double, мягко говоря, некорректный ни разу...
Прошу прощения, дерьмо посоветовал...
Re[4]: Преобразовать System.Double в обыкновенную дробь
П>Однако и глючные либы выкладывают ребята из BCL:
П>То есть импорт из double, мягко говоря, некорректный ни разу... П>Прошу прощения, дерьмо посоветовал...
Да ладно, главное идея, а она там такова: сначала нужно расчленить Double на мантиссу, знак и степень, а потом на основании этих значений получить числитель и знаменатель дроби. Вопрос в том, имеет ли это смысл, ведь степень всё равно может оказаться -308. Тут по любому на 10^308 придётся умножать. А расчленять double — тоже затратно. Не эффективнее ли работать по алгоритму из первого поста?
Re: Преобразовать System.Double в обыкновенную дробь
Здравствуйте, Mak_71_rus, Вы писали:
M__>Здравствуйте! M__>Помогите пожалуйста решить задачу: нужно преобразовать число типа System.Double в обыкновенную дробь, т.е. найти числитель и знаменатель этой дроби (они имеют тип System.Numerics.BigInteger).
M__>У меня есть только такая мысль: M__>1) выделить целую часть и записать её во временной переменной типа System.Numerics.BigInteger; M__>2) дробную часть умножить на 10^38 (значок ^ обозначает возведение в степень) и записать полученное значение в числитель; M__>3) знаменателю присвоить значение 10^38; M__>4) сократить полученную дробь; M__>5) временную переменную умножить на знаменатель, потом прибавить числитель и результат записать в числитель.
Есть очень простой алгоритм, позволяющий приблизить десятичную дробь простой дробью с нужной точностью. Он в свое время публиковался еще в "Науке и жизни" с программой для ПМК. Итак (псевдокод):
d = 0.12345; // Исходная дробь, может быть любой
a0 = 0; a1 = 1;
b0 = 1; b1 = 0;
while(не_достигнута_нужная точность)
{
N = Floor(d);
a = N * a1 + a0
b = N * b1 + b0;
printf("%d / %d = %f\n", a, b, a/b);
a0 = a1;
a1 = a;
b0 = b1;
b1 = b;
d = 1/(d - N);
}
Здравствуйте, Васильич, Вы писали:
В>Есть очень простой алгоритм, позволяющий приблизить десятичную дробь простой дробью с нужной точностью. Он в свое время публиковался еще в "Науке и жизни" с программой для ПМК. Итак (псевдокод):
В>
В>d = 0.12345; // Исходная дробь, может быть любой
В>a0 = 0; a1 = 1;
В>b0 = 1; b1 = 0;
В>while(не_достигнута_нужная точность)
В>{
В> N = Floor(d);
В> a = N * a1 + a0
В> b = N * b1 + b0;
В> printf("%d / %d = %f\n", a, b, a/b);
В> a0 = a1;
В> a1 = a;
В> b0 = b1;
В> b1 = b;
В> d = 1/(d - N);
В>}
В>
Алгоритм хорош, только если нужно приближать с небольшой точностью. А double может хранить числа порядка 10^-308 Если в алгоритме задать такую точность, он будет выполняться несколько часов.
Re[5]: Преобразовать System.Double в обыкновенную дробь
Здравствуйте, Mak_71_rus, Вы писали:
M__>Да ладно, главное идея, а она там такова: сначала нужно расчленить Double на мантиссу, знак и степень, а потом на основании этих значений получить числитель и знаменатель дроби. Вопрос в том, имеет ли это смысл, ведь степень всё равно может оказаться -308. Тут по любому на 10^308 придётся умножать. А расчленять double — тоже затратно.
Не очень затратно. Правда, на С++
frexp
Gets the mantissa and exponent of a floating-point number.
double frexp(
double x,
int *expptr
);
float frexp(
float x,
int * expptr
); // C++ only
long double frexp(
long double x,
int * expptr
); // C++ only
frexp returns the mantissa. If x is 0, the function returns 0 for both the mantissa and the exponent. If expptr is NULL, the invalid parameter handler is invoked as described in Parameter Validation. If execution is allowed to continue, this function sets errno to EINVAL and returns 0.
Remarks
The frexp function breaks down the floating-point value (x) into a mantissa (m) and an exponent (n), such that the absolute value of m is greater than or equal to 0.5 and less than 1.0, and x = m*2n. The integer exponent n is stored at the location pointed to by expptr.
Example
// crt_frexp.c
// This program calculates frexp( 16.4, &n )
// then displays y and n.
#include <math.h>
#include <stdio.h>
int main( void )
{
double x, y;
int n;
x = 16.4;
y = frexp( x, &n );
printf( "frexp( %f, &n ) = %f, n = %d\n", x, y, n );
}
frexp( 16.400000, &n ) = 0.512500, n = 5
Нахождение знака оставляю в качестве самостоятельного упражнения
With best regards
Pavel Dvorkin
Re[3]: Преобразовать System.Double в обыкновенную дробь
От:
Аноним
Дата:
05.09.10 16:28
Оценка:
Здравствуйте, Mak_71_rus, Вы писали:
M__>Алгоритм хорош, только если нужно приближать с небольшой точностью. А double может хранить числа порядка 10^-308 Если в алгоритме задать такую точность, он будет выполняться несколько часов.
Такая точность практически никогда не требуется. Хуже того, если попробовать разложить 0.12344 методом умножения на 10^308 и последующим нахождением НОД, то будет получена дробь вида 12344000000...0000001/100000000...000000, так как 0.12344 не представляется в double прямо в таком виде. Кроме того защищаемый вами алгоритм более затратен по памяти и по процессорному времени. Стоит оно того?
Re[4]: Преобразовать System.Double в обыкновенную дробь
12344000000...0000001/100000000...000000, так как 0.12344 не представляется в double прямо в таком виде. Кроме того защищаемый вами алгоритм более затратен по памяти и по процессорному времени. Стоит оно того?
Да нет же!!! Не защищаю я его не в коем случае, это первое, что пришло в голову, я понимаю, что он крайне не рационален. Дело в том, что тип обыкновенная дробь шире типа Double и поэтому хотелось бы чтобы он умел представлять любое значение, которое может представлять Double, как Int32 представляет любое значение Int16.
Re: Преобразовать System.Double в обыкновенную дробь
Здравствуйте, Mak_71_rus, Вы писали:
M__>Здравствуйте! M__>Помогите пожалуйста решить задачу: нужно преобразовать число типа System.Double в обыкновенную дробь, т.е. найти числитель и знаменатель этой дроби (они имеют тип System.Numerics.BigInteger).
Так она и есть простая дробь m*2^(e-1023), +/-m = [1.1125369292536006915451163586662e-308;1.797693134862315907729305190789e+308], e = [0;2047] (насчёт m точно не помню), m, e целые числа.
M__>Мне кажется, что можно сделать более рационально.
дели или умножай на 2 вот пример на VB.Net:
Sub Main()
Dim d As Double, dbl As Double, num As Int64, den As Int64
d = (New Random()).NextDouble() * 1.0E+16 ' задаёшь число.
dbl = d
den = 1
If d < 18014398509481984.0 Then
Do Until System.Math.Floor(dbl) = dbl
den *= 2
dbl *= 2
Loop
Else
Do Until (dbl / 2) - System.Math.Floor(dbl / 2) > 0
den *= 2
dbl /= 2
Loop
End If
num = System.Math.Floor(dbl)
' Тут можно посчитать НОД и сократить дробь.
Console.WriteLine(d & "=" & num & "/" & den)
Console.ReadKey()
End Sub
Наука изощряет ум; ученье вострит память.
(c) Козьма Прутков
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Здравствуйте, Mak_71_rus, Вы писали:
M__>>Да ладно, главное идея, а она там такова: сначала нужно расчленить Double на мантиссу, знак и степень, а потом на основании этих значений получить числитель и знаменатель дроби. Вопрос в том, имеет ли это смысл, ведь степень всё равно может оказаться -308. Тут по любому на 10^308 придётся умножать. А расчленять double — тоже затратно.
PD>Не очень затратно. Правда, на С++
PD>frexp
PD>Gets the mantissa and exponent of a floating-point number.
PD>double frexp( PD> double x, PD> int *expptr PD>); PD>float frexp( PD> float x, PD> int * expptr PD>); // C++ only PD>long double frexp( PD> long double x, PD> int * expptr PD>); // C++ only
PD>frexp returns the mantissa. If x is 0, the function returns 0 for both the mantissa and the exponent. If expptr is NULL, the invalid parameter handler is invoked as described in Parameter Validation. If execution is allowed to continue, this function sets errno to EINVAL and returns 0.
PD>Remarks PD>The frexp function breaks down the floating-point value (x) into a mantissa (m) and an exponent (n), such that the absolute value of m is greater than or equal to 0.5 and less than 1.0, and x = m*2n. The integer exponent n is stored at the location pointed to by expptr.
PD>Example PD>// crt_frexp.c PD>// This program calculates frexp( 16.4, &n ) PD>// then displays y and n.
PD>#include <math.h> PD>#include <stdio.h>
PD>int main( void ) PD>{ PD> double x, y; PD> int n;
PD> x = 16.4; PD> y = frexp( x, &n ); PD> printf( "frexp( %f, &n ) = %f, n = %d\n", x, y, n ); PD>}
PD>frexp( 16.400000, &n ) = 0.512500, n = 5
PD>Нахождение знака оставляю в качестве самостоятельного упражнения
Вот такую frxp() надо реализовать на C#. Думаю использовать структуру, состоящую из double и Int64 c помощбю атрибута задоть нулевое смещение и сдвигами разделять на мантиссу и степень.
Re[3]: Преобразовать System.Double в обыкновенную дробь
Здравствуйте, Mak_71_rus, Вы писали:
M__>Алгоритм хорош, только если нужно приближать с небольшой точностью. А double может хранить числа порядка 10^-308 Если в алгоритме задать такую точность, он будет выполняться несколько часов.
double сам по себе не особо точный, так что алгоритм вполне рабочий для преобразований типа 1/3 в double и обратно.
Re[7]: Преобразовать System.Double в обыкновенную дробь
M__>Вот такую frxp() надо реализовать на C#. Думаю использовать структуру, состоящую из double и Int64 c помощбю атрибута задоть нулевое смещение и сдвигами разделять на мантиссу и степень.
Попробуй . Но дело в том, что С-шная frexp есть просто inline функция для команды FPU FXTRACT.
