Как вычислить первую десятичную цифру деления между большими числами?

Question

У меня есть два unsigned long longs X и Y, где X < Y, но оба могут быть очень большими. Я хочу вычислить первую цифру после десятичной точки X/Y. Например, если X равно 11, а Y равно 14, тогда 11/14 составляет .785 ..., поэтому результат должен быть равен 7.

(X * 10)/Y будет работать, за исключением того, что он производит неправильный результат, если X * 10 переполняется. Преобразование в double будет работать, если у меня есть основания полагать, что он достаточно точен, чтобы вычислить правильный результат.

Это в С. Спасибо за любую помощь!

Answer 1

Конверсия в double будет работать, если у меня есть основания полагать, что она достаточно точная, чтобы вычислить правильный результат.

Если вам нужна только первая цифра, то, безусловно, двойная точность достаточно.

Редактировать: Противоположный пример wrang-wrang в комментариях доказывает, что я ошибаюсь.

Answer 2

Я не желаю гарантировать точный результат с помощью приведения с плавающей запятой, если у мантиссы достаточно бит, чтобы точно представлять все интегральные значения. Например, tonider y = 9223372036854775807 и x = (y div 10) - 1 = 922337203685477579. где «div» - целочисленное деление. x/y - 0.09999999999999999981568563067746 ..., но с использованием парного разряда вы получаете => 0,1. Это результат удвоения, имеющего только 52 цифры точности в значении (в то время как y требует 61 бит и x около 58)

Возможно, вы сможете использовать точность 80 бит или 128 бит FP, и в этом случае вы получите правильный ответ, потому что мантисса будет> = 64 бит (ULL - 64-битный, верно?), и поэтому вы без потерь представляете числа.

Я бы начал с приближения (используя целочисленную или Арифметическую Арифметику), а затем пробное умножение, чтобы увидеть, должен ли ответ быть меньше или меньше. Ключевое понимание состоит в том, что вы все равно можете сравнить два, возможно, переполненных ints, если знаете, что разница между этими двумя величинами меньше половины max unsigned int. Такой метод сравнения необходим, когда, например, Переполнение номеров последовательностей TCP.

Если вы хотите использовать только целочисленная арифметика, работает нижняя функция «fdd (x, y)». Я включил основные(), чтобы показать некоторые результаты:

#include <iostream> 
using namespace std; 

typedef unsigned char ull; // change char to any integral type e.g. long long 

const ull maxull=(ull)-1; 
const ull halfull = maxull/2; 
typedef unsigned long long asint; 

// x = X mod (maxull+1), y= Y mod (maxull+1). we only know x and y 
// if we assume |X-Y|<halfull, then we return X<Y: 
inline bool less_mod_near(ull x, ull y) { 

    return (x<=halfull == y<=halfull) ? x<y : y>x; 
} 

// assuming x<y, return first decimal digit of 10x/y (return is in [0..9]) 
inline int fdd(ull x, ull y) { 
// assert(x<y); 
if (x<=maxull/10) return (10*x)/y; 
    // for speed, and to ensure that y>10 to avoid division by 0 later 
ull r=y/10; 
if (r*10==y) return x/r; 
ull ub=x/(r+1); // ub >= 10x div y (without overflow) 
ull x10=x*10; // allow overflow 
cout<<"ub="<<(asint)ub<<" x10="<<(asint)x10<<" r="<<(asint)r<<" "; 
return less_mod_near(x10,ub) ? ub-1 : ub; 
    // we already handled the 10 evenly divides y case 
} 

int pdd(ull x, ull y,ull mustbe) 
{ 
    ull d=fdd(x,y); 
    cout << (asint)x << '/' << (asint)y << " = ." << (asint)d << "..."; 
    if (d!=mustbe) cout << " (should be "<<(asint)mustbe<<")"; 
    cout<<endl; 
// assert(a==d); 
} 

int main() { 
    pdd(0,1,0); 
    pdd(1,2,5); 
    pdd(11,101,1); 
    pdd(10,101,0); 
    pdd(49,69,7); 
    pdd(50,69,7); 
    pdd(48,69,6); 
    pdd(160,200,8); 
    pdd(161,200,8); 
    pdd(159,200,7); 
    pdd(254,255,9); 
} 

Выход:

0/1 = .0... 
1/2 = .5... 
11/101 = .1... 
10/101 = .0... 
ub=7 x10=234 r=6 49/69 = .7... 
ub=7 x10=244 r=6 50/69 = .7... 
ub=6 x10=224 r=6 48/69 = .6... 
160/200 = .8... 
161/200 = .8... 
159/200 = .7... 
ub=9 x10=236 r=25 254/255 = .9... 

Answer 3

Преобразование Double собирается отказаться от 12-бит точности как на дивиденд и donominator из 64. Большую часть времени он даст вам правильный ответ, однако он будет иметь округленные ошибки, если он не будет храниться в 80-битном плавающем формате.

Редактировать: Если я не слишком сонный, чтобы увидеть ошибку, я думаю, что ответ отряда-бранда будет работать. У меня есть работа утром, 6 часов езды на сайт клиента. Ugg. ночь.

Редактировать: Последнее. x86 использует внутреннее представление 80 бит. Я думаю, что есть коды операций, которые преобразуют преобразование int64 в float80, если вы хотите бросить пару инструкций asm. Это было бы более элегантным и, безусловно, более быстрым решением, чем чистая реализация C, хотя она не была бы переносимой.

Answer 4

X% Y дает остаток R

Вы можете вычислить дробную часть вашего ответа от R и Y

R/Y 

Чтобы получить 1-й разряд использование целочисленное деление:

(long)((long)10*R/Y) 

Это должно округлить цифры и отбросить любые дополнительные десятичные знаки.

Edit:

Чтобы соответствовать ваш вопрос (для тех, кто хочет быть придирчивым) его

Y % X = R 

и

R/X 

Answer 5

Если вы prpared принять ограничение диапазона вы можете сделать все это целое число arithmatic: -

(Х * 10)/Y

В вашем примере:

(11 * 10)/14 

=> 110/14

=> 7

исковой быть вы уменьшили максимальное значение X в 10 раз.

Answer 6

Как насчет

x/((y + 9)/10) 

Y + 9 предназначен для округления коэффициента y/10 в знаменателе, поэтому общий результат округляется.

Для больших х и у него должно быть почти всегда правильно, но она не совершенна, она производит 5 для примера 11/14.

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