恒定时间长数的前N位数？

Question

在Project Euler问题中,我需要处理可能有数百个数字的数字.我需要对前9位进行一些计算.

我的问题是:确定100位整数的前N位数的最快方法是什么？模数/余数的前N位数很容易.对于第一个数字,我可以按模数应用模数100次,或者我可以将数字转换为字符串并截断,但它们都是线性时间.有没有更好的办法？

Answer 1

您可以使用此功能计算位数:

(defn dec-digit-count [n]
  (inc (if (zero? n) 0
  (long (Math/floor (Math/log10 n))))))

现在我们知道有多少位数,我们只想先离开9.我们必须将数字除以10 ^(数字-9)或在Clojure中:

(defn first-digits [number digits]
  (unchecked-divide number (int (Math/pow 10 digits))))

并称之为:(first-digits your-number 9)我认为这是在不断的时间.我只是不确定log10实施.但是,模数/循环解决方案肯定要快得多.

此外,还有一个更简单的解决方案.您只需复制并粘贴该数字的前9位数即可.