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))))
4

2 に答える 2

4

Rustでどのように解決しますか？Rust の int も最大で 64 ビットにする必要があります。あなたの関数では、が 10000000000fになると少し難しくなります。いくつかの選択肢があります。n

いくつかのスタイルの変更:

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)))
于 2015-07-10T19:52:42.817 に答える
2

bignum パッケージもご覧ください: https://github.com/FedeOmoto/bignum

これは nim-gmp の高レベルのラッパーであるため、さまざまなプログラミング モデルのような低レベルのものを扱う必要はありません (GMP は長い C 型を広範囲に使用するため、Win64 - LLP64 をターゲットにする場合は少し面倒です)。

于 2015-07-19T23:14:12.303 に答える