Geek Answers Handbook

The most efficient way to get a number number of an arbitrarily large number

What is the most efficient way to get the digits of a number?

Let's start with an example:

Imagine a Fibonacci sequence. Now let me say that we want to know which Fibonacci number is the first to have 1000 digits (in base representation 10). Up to 308 digits (1476th Fibonacci number) we can easily do this using logBase 10 <number>. If the number is greater than the 1476th Fibonacci number, it logBasewill return Infinity, and the calculation will fail. The problem is that the 308 is a little far from 1000, which was our original goal.

A possible solution is to convert the number we want to know about the number of digits of the string, and use it to determine the number of digits. This is a little ineffective for my purposes, because trying it with 10,000 takes its sweet time.

The most effective method shown in other issues is hard coding of all possible cases that I really do not want to do, especially since the number of digits exceeds 10, if necessary in the proposed solutions.

So, to get back to my question: what is the best (most efficient) way to determine a digit of a digit at 10 digits? Is it really converting it to a string and using its length or are there any “hacking" tricks like 0x5f3759df ?

. , "haskell".

+4
4

div, 10?

digitCount :: Integer -> Int
digitCount = go 1 . abs
    where
        go ds n = if n >= 10 then go (ds + 1) (n `div` 10) else ds

O(n), n - , , 1000, 100, 10, , , .

, , GHCi :set +s:

> let x = 10 ^ 10000 :: Integer
> :force x
<prints out 10 ^ 10000>
> digitCount x
10001
it :: Int
(0.06 secs, 23759220 bytes)

, 10001 10 .

O(log(n)), , 2, , 10. 20000 .

+7

digitCount , O(1), fibBeingTested >= 10digitCount - 1. , 10digitCount - 1 - digitCount :

import Data.List (find)

fibs :: [Integer]
-- ...

findFib :: Int -> Integer
findFib digitCount =
  let Just solution = find (>= tenPower) fibs
  in
  solution
  where
    tenPower = 10 ^ (digitCount - 1)

digitCount - 1, 10^1, , 10, .

O(1), , . :

λ> :set +s
λ> findFib 10000
[... the first Fibonacci number with at least 10,000 digits ...]
(0.23 secs, 121255512 bytes)

fibs 10,000th (, findFib 10000), , , , :

λ> findFib 10000   -- Second run of findFib 10000
[... the first Fibonacci number with at least 10,000 digits ...]
(0.04 secs, 9922000 bytes)
+2

, 1000 , length . show (on Integer).

GHCi> let fibs = Data.Function.fix $ (0:) . scanl (+) 1
GHCi> let digits = length . (show :: Integer -> String)
GHCi> :set +t +s
GHCi> fst . head . dropWhile ((1000>) . digits . snd) $ zip [0..] fibs
4782
it :: Integer
(0.10 secs, 149103264 bytes)

( logBase) Double look numbers. , - .

0

You can always try binary search to find the number of digits n: first find ak, so that 10 ^ 2 ^ k ≥ n, and then divide n successfully by 10 ^ 2 ^ (k-1), 10 ^ 2 ^ (k- 2), ..., 10 ^ 2 ^ 0:

numDigits n = fst $ foldr step (1,n) tenToPow2s
  where
    pow2s = iterate (*2) 1
    tenToPow2s = zip pow2s . takeWhile (<=n) . iterate (^2) $ 10
    step (k,t) (d,n) = if n>=t then (d+k, n `div` t) else (d,n)

For a specific case of Fibonacci numbers, you can also just try the math: the nth Fibonacci number F (n) is between (φ ^ n-1) / √5 and (φⁿ + 1) / √5, so for base 10 logarithm:

log (F (n)) - n log (φ) + log (√5) ∈ [log (1 - 1 / φⁿ), log (1 + 1 / φⁿ)]

This interval immediately becomes tiny.

0
source

More articles:


All Articles