2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Существует ли способ найти заданную цифру в дроби?
Сообщение25.01.2013, 22:45 
Добрый вечер, возник вопрос, сущесвует ли способ быстро посчитать заданную цифру в дроби?

Например,

$\frac{1}{7} = 0,(142857)$

можно ли быстро, желательно за $O(1)$, получить 3-ую цифру после запятой, т.е. 2?

 
 
 
 Posted automatically
Сообщение26.01.2013, 20:20 
Аватара пользователя
За $O(1)$ Вы, очевидно, не сможете получить произвольную $k$-ю цифру дроби, поскольку за $O(1)$ можно вычислить лишь конечное, не зависящее от $k$, число цифр дроби.
Если обозначить период дроби $T$, то достаточно $O(T)$ операций. Однако, если $n$ - простое, то $T=n-1$ тогда и только тогда, когда $10$ (основание $10$-ичной системы счисления) - первообразный корень по модулю $n$. Согласно гипотезе Артина, таких простых $n$ бесконечно много. Предполагая истинной гипотезу Артина, получаем $O(T)=O(n)$.
Короче говоря, я не вижу ничего лучше, чем просто вычислить десятичную дробь с точностью $10^{-k}$ и взять $k$-ю цифру числа.

 
 
 
 Re: Существует ли способ найти заданную цифру в дроби?
Сообщение26.01.2013, 20:27 
Разумеется. Считаем цифры в периоде — определяем длину периода — профит.

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group