避免 Nim 中的整数溢出

Question

我昨天开始学习 Nim，并决定编写一个小测试来与 Rust 进行性能比较。该代码相当容易编写，适用于高达 10^9 的值。但是，我需要至少使用 10^12 对其进行测试，即使在使用 uint 时也会因为溢出而给出不正确的值。

我一直在尝试对大多数变量进行不同的转换，但我似乎无法避免溢出。当然，我们非常欢迎任何使代码更易于阅读的建议！

import math
import sequtils
import unsigned

proc sum_min_pfactor(N : uint) : uint =
    proc f(n : uint) : uint =
        return n*(n+1) div 2 - 1
    var
        v = int(math.sqrt(float(N)))
        used = newSeqWith(v+1,false)
        s_sum,s_cnt,l_cnt,l_sum = newSeq[uint](v+1)
        ret = 0.uint
    for i in -1..v-1:
        s_cnt[i+1] = i.uint
    for i in 0..v:
        s_sum[i] = f(i.uint)
    for i in 1..v:
        l_cnt[i] = N div i.uint - 1
        l_sum[i] = f(N div i.uint)
    for p in 2..v:
        if s_cnt[p] == s_cnt[p-1]:
            continue
        var p_cnt = s_cnt[p - 1]
        var p_sum = s_sum[p - 1]
        var q = p * p
        ret += p.uint * (l_cnt[p] - p_cnt)
        l_cnt[1] -= l_cnt[p] - p_cnt
        l_sum[1] -= (l_sum[p] - p_sum) * p.uint
        var interval = (p and 1) + 1
        var finish = min(v,N.int div q)
        for i in countup(p+interval,finish,interval):
            if used[i]:
                continue
            var d = i * p
            if d <= v:
                l_cnt[i] -= l_cnt[d] - p_cnt
                l_sum[i] -= (l_sum[d] - p_sum) * p.uint
            else:
                var t = N.int div d
                l_cnt[i] -= s_cnt[t] - p_cnt
                l_sum[i] -= (s_sum[t] - p_sum) * p.uint
        if q <= v:
            for i in countup(q,finish-1,p*interval):
                used[i] = true
        for i in countdown(v,q-1):
            var t = i div p
            s_cnt[i] -= s_cnt[t] - p_cnt
            s_sum[i] -= (s_sum[t] - p_sum) * p.uint
    return l_sum[1] + ret

echo(sum_min_pfactor(uint(math.pow(10,2))))

Answer 1

你是怎么用Rust解决的？ Rust 的 int 最多也应该是 64 位的。在您的 f 函数中，当 n 为 10000000000 时，它会变得有点困难。您有几个选择：

您可以改用浮点数，但精度较低
您可以使用 int128，但性能较低：https://bitbucket.org/nimcontrib/NimLongInt/src
或者您可以使用 bigints：
- https://github.com/FedeOmoto/nim-gmp（高性能，取决于 GMP）
- https://github.com/def-/nim-bigints（性能低，用Nim写的，测试不多）

一些风格上的变化：

import math

proc sum_min_pfactor(N: int): int =
  proc f(n: int): int =
    n*(n+1) div 2 - 1

  var
    v = math.sqrt(N.float).int
    s_cnt, s_sum, l_cnt, l_sum = newSeq[int](v+1)
    used = newSeq[bool](v+1)

  for i in 0..v: s_cnt[i] = i-1
  for i in 1..v: s_sum[i] = f(i)
  for i in 1..v: l_cnt[i] = N div i - 1
  for i in 1..v: l_sum[i] = f(N div i)

  for p in 2..v:
    if s_cnt[p] == s_cnt[p-1]:
      continue

    let
      p_cnt = s_cnt[p - 1]
      p_sum = s_sum[p - 1]
      q = p * p

    result += p * (l_cnt[p] - p_cnt)
    l_cnt[1] -= l_cnt[p] - p_cnt
    l_sum[1] -= (l_sum[p] - p_sum) *  p

    let interval = (p and 1) + 1
    let finish = min(v,N div q)

    for i in countup(p+interval,finish,interval):
      if used[i]:
        continue
      let d = i * p
      if d <= v:
        l_cnt[i] -= l_cnt[d] - p_cnt
        l_sum[i] -= (l_sum[d] - p_sum) * p
      else:
        let t = N div d
        l_cnt[i] -= s_cnt[t] - p_cnt
        l_sum[i] -= (s_sum[t] - p_sum) * p

    if q <= v:
      for i in countup(q,finish-1,p*interval):
        used[i] = true

    for i in countdown(v,q-1):
      let t = i div p
      s_cnt[i] -= s_cnt[t] - p_cnt
      s_sum[i] -= (s_sum[t] - p_sum) * p

  result += l_sum[1]

for i in 2..12:
  echo sum_min_pfactor(int(math.pow(10,i.float)))

Answer 2

也请看一下 bignum 包：https://github.com/FedeOmoto/bignum

它是 nim-gmp 的高级包装器，因此您不必处理不同编程模型等低级内容（GMP 广泛使用 long C 类型，因此在针对 Win64 - LLP64 时有点麻烦） .

避免 Nim 中的整数溢出

Avoiding integer overflow in Nim

performance

overflow

performance-testing

nim-lang