Нахождение кубического корня большого числа - PullRequest
Новая
       3

Нахождение кубического корня большого числа

0 голосов
/ 05 декабря 2010

Мне нужно найти корень куба огромного (5k бит или около того) числа, округленного вверх.Как мне это сделать?

Ответы [ 2 ]

5 голосов
/ 05 декабря 2010

Если GNU bc подходит вам, это может подойти:

http://phodd.net/gnu-bc/bcfaq.html#bccbrt

EDIT:

Это, по сути, сводится к: 

$ bc -l
define cbrt(x) { return e(l(x)/3) }

Вам потребуется увеличить переменную масштаба, чтобы получить необходимую точность: 

$ bc -l
bc 1.06.95
Copyright 1991-1994, 1997, 1998, 2000, 2004, 2006 Free Software Foundation, Inc.
This is free software with ABSOLUTELY NO WARRANTY.
For details type `warranty'.

define cbrt(x) { return e(l(x)/3) }

cbrt(10000000000000000000000000000000000000000000000000000000000000000000)^3
9999999999999999999845725361475980907263179272258247094885777761435.\
89049462743995306310

scale=1000

cbrt(10000000000000000000000000000000000000000000000000000000000000000000)^3
9999999999999999999999999999999999999999999999999999999999999999999.\
99999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999999999999999999999999\
99999999999999999999999999999999999999999999999978254573198390239858\
069738839057154871628814670160708326688382280410

Как вы, наверное, заметили, без увеличения переменной масштаба (в моей системе по умолчанию она равна 20) результат не достигнет необходимой вам точности.

0 голосов
/ 05 декабря 2010

Вот простой итерационный алгоритм . Обратите внимание, что они указывают на особый случай квадратных корней :

Особый случай - знакомый алгоритм квадратного корня. Установив n = 2, правило итерации на шаге 2 становится правилом итерации квадратного корня

Та же самая техника может быть применена к корням куба: установите n = 3 и повторяйте, пока не достигнете желаемой точности .

В случае спецификации в комментарии «его необходимо округлить до ближайшего целого числа и быть точным», что будет возможно только для чисел, имеющих целочисленные или рациональные корни куба. Тем не менее, вы можете использовать процитированный алгоритм, чтобы найти ответ на этот уровень точности путем итерации, пока разница между результатом одной итерации и следующей не станет меньше 0,5. Это достаточно близко, чтобы гарантировать, что будущие итерации не отклонятся далеко от этого приближения.

Это упражнение для класса численного анализа? Если так, я подозреваю, что именно поэтому вопрос был задан таким образом: инструктор хотел бы, чтобы вы применили общее правило к конкретной проблеме.

...