在Nim中避免整数溢出

Question

在Nim中避免整数溢出

performanceoverflowperformance-testingnim-lang

4

我昨天开始学习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))))

- Nicolás Siplis

2个回答

2

请也查看bignum包：https://github.com/FedeOmoto/bignum 这是nim-gmp的高级封装，因此您无需处理低级别的东西，例如不同的编程模型（GMP广泛使用长C类型，因此在针对Win64 - LLP64时有点麻烦）。

- Federico Omoto

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- def- · Accepted Answer

你如何在Rust中解决这个问题？ Rust的整数最多也应该是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)))