标签: arbitrary-precision

我一直在使用python的本机bignums算法,并决定尝试通过将其转换为C++来加速它.当我使用long long时,C++比python快约100倍,但是当我在C++中使用GMP绑定时,它只比python快10倍(适用于长long的相同情况).

是否有更好的bignum实现来进行大量的小额外添加？例如,我们有一个很大的数字N我们将添加很多小+1,+ 21,+ 1等等,并且每隔一段时间又增加一个大数字M？

Ruby怎么做到这一点？Jörg或其他任何人都知道幕后发生了什么吗？

不幸的是我不太了解C,所以bignum.c对我没什么帮助.我有点好奇,有人可以用简单的英语解释它使用的奇迹算法背后的理论.

irb(main):001:0> 999**999

368063488259223267894700840060521865838338232037353204655959621437025609300472231530103873614505175218691345257589896391130393189447969771645832382192366076536631132001776175977932178658703660778465765811830827876982014124022948671975678131724958064427949902810498973271030787716781467419524180040734398996952930832508934116945966120176735120823151959779536852290090377452502236990839453416790640456116471139751546750048602189291028640970574762600185950226138244530187489211615864021135312077912018844630780307462205252807737757672094320692373101032517459518497524015120165166724189816766397247824175394802028228160027100623998873667435799073054618906855460488351426611310634023489044291860510352301912426608488807462312126590206830413782664554260411266378866626653755763627796569082931785645600816236891168141774993267488171702172191072731069216881668294625679492696148976999868715671440874206427212056717373099639711168901197440416590226524192782842896415414611688187391232048327738965820265934093108172054875188246591760877131657895633586576611857277011782497943522945011248430439201297015119468730712364007639373910811953430309476832453230123996750235710787086641070310288725389595138936784715274150426495416196669832679980253436807864187160054589045664027158817958549374490512399055448819148487049363674611664609890030088549591992466360050042566270348330911795487647045949301286614658650071299695652245266080672989921799342509291635330827874264789587306974472327718704306352445925996155619153783913237212716010410294999877569745287353422903443387562746452522860420416689019732913798073773281533570910205207767157128174184873357050830752777900041943256738499067821488421053870869022738698816059810579221002560882999884763252161747566893835178558961142349304466506402373556318707175710866983035313122068321102457824112014969387225476259342872866363550383840720010832906695360553556647545295849966279980830561242960013654529514995113584909050813015198928283202189194615501403435553060147713139766323195743324848047347575473228198492343231496580885057330510949058490527738662697480293583612233134502078182014347192522391449087738579081585795613547198599661273567662441490401862839817822686573112998663038868314974259766039340894024308383451039874674061160538242392803580758232755749310843694194787991556647907091849600704712003371103926967137408125713631396699343733288014254084819379380555174777020843568689927348949484201042595271932630685747613835385434424807024615161848223715989797178155169951121052285149157137697718850449708843330475301440373094611119631361702936342263219382793996895988331701890693689862459020775599439506870005130750427949747071390095256759203426671803377068109744629909769176319526837824364926844730545524646494321826241925107158040561607706364484910978348669388142016838792902926158979355432483611517588605967745393958061959024834251565197963477521095821435651996730128376734574843289089682710350244222290017891280419782767803785277960834729869249991658417000499998999

我有一个长整数,但它不是以十进制形式存储,而是存储为余数.

所以,我没有这个N数字,而是一组这样的剩余部分:

r_1 = N % 2147483743
r_2 = N % 2147483713
r_3 = N % 2147483693
r_4 = N % 2147483659
r_5 = N % 2147483647
r_6 = N % 2147483629

我知道,N小于这些素数的乘法,所以中文余数定理在这里起作用(http://en.wikipedia.org/wiki/Chinese_remainder_theorem).

N如果我有这6个余数,我怎么能以十进制恢复？精彩的将是任何程序(C/C + GMP/C++/perl/java/bc).

例如,最小N可以有这组余数:

r_1 = 1246736738 (% 2147483743)
r_2 = 748761 (% 2147483713)
r_3 = 1829651881 (% 2147483693)
r_4 = 2008266397 (% 2147483659)
r_5 = 748030137 (% 2147483647)
r_6 = 1460049539 (% 2147483629)

什么是可伸缩算法来手动打印其值不适合的N二进制数字整数long long.我知道printf和朋友一起<iostream>(最有可能的背驮式<cstdio>有内置的标准类型,但我想为一个由N个字节组成的整数.

我已经考虑过这个并且用谷歌搜索了一下,但它总是归结为使用像GMP这样的预先存在的bigint图书馆(我根本不熟悉的代码库)或"使用printf"或者最有用的"这很难" .

整数基本上是:

template<size_t N>
class Integer{
...
private:
    int8_t first;
    uint8_t rest[N-1];
}

所以重新解释一个Integer<4>字节可以得到你int32_t.我想把它缩放到N> 8.目前效率并不是我真正关心的问题.也不是字节序(这是针对x86).

对于某些人来说,这可能是一个非常简单的问题,但我想知道BigInteger的 JavaDoc第一行中出现的任意精度的含义:

不可变的任意精度整数.

我正在尝试以大于双精度的固定精度在Scala(和/或Java)中进行计算.我正在使用带有Scala默认MathContext的 BigDecimals ,它具有精度34.即使所有输入都具有这种精度,我发现经过一些计算后,结果的精度开始爆炸.

这是一个示例计算,我认为说明了问题:

import math.BigDecimal

val z40 = BigDecimal(0).setScale(40) // 0E-40
z40.scale                            // 40
z40.precision                        // 1
(1 + z40*z40).precision              // 81

结果是81,精度高于z40.在我的例子中,我从不使用setScale,但是计算中出现了具有非常大比例的零.

这不是我想要的行为.我想要(1 + z40*z40)精度34 - 正在执行计算的MathContext的精度(因为z40*z40与1相比可以忽略不计).我怎么能得到这种算术？

更新:此行为是由于Scala 2.9.*和2.10.*之间的MathContexts处理的更改.(感谢Paul Phillips指出了提交.)另见本讨论.

我需要以任意精度获取值的哈希值(来自Boost.Multiprecision); 我用cpp_int后端.现在,我想出了以下代码:

boost::multiprecision::cpp_int x0 = 1;
const auto seed = std::hash<std::string>{}(x0.str());

我不需要代码尽可能快,但我发现散列字符串表示非常笨拙.

所以我的问题是双重的:

• 保持任意精度,我可以更有效地散列值吗？
• 也许我不应该坚持保持任意精度,我应该转换为double我可以轻松散列(我仍然会使用任意精度值进行哈希表所需的比较)？

假设您想使用来知道W数字的前有效数字，例如pi vpa。仅仅vpa用那么多的数字打电话是行不通的。考虑以下示例W = 35：

>> disp(vpa(sym('pi'), 35))
3.1415926535897932384626433832795029

四舍五入的原因。具体来说，以上结果似乎表明35pi 的-th有效数字是9，而实际上是四舍五入的8：

>> disp(vpa(sym('pi'), 36))
3.14159265358979323846264338327950288

从上面看来，一种解决方案似乎是要求再增加一个十进制数并将其丢弃，以使最后一个尚存的十进制数没有舍入问题。但是这并不能在一般的工作之一，因为舍入可引起携带。请参阅Matlab中的以下示例：

>> disp(vpa(sym('pi'), 79))
3.141592653589793238462643383279502884197169399375105820974944592307816406286209
>> disp(vpa(sym('pi'), 80))
3.141592653589793238462643383279502884197169399375105820974944592307816406286209
>> disp(vpa(sym('pi'), 81))
3.141592653589793238462643383279502884197169399375105820974944592307816406286209
>> disp(vpa(sym('pi'), 82))
3.141592653589793238462643383279502884197169399375105820974944592307816406286208999
>> disp(vpa(sym('pi'), 83))
3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986

或八度音阶：

>> disp(vpa(sym('pi'), 79))
3.141592653589793238462643383279502884197169399375105820974944592307816406286209
>> disp(vpa(sym('pi'), 80))
3.1415926535897932384626433832795028841971693993751058209749445923078164062862090
>> disp(vpa(sym('pi'), 81))
3.14159265358979323846264338327950288419716939937510582097494459230781640628620900
>> disp(vpa(sym('pi'), 82))
3.141592653589793238462643383279502884197169399375105820974944592307816406286208999
>> disp(vpa(sym('pi'), 83))
3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986

可以看出，

• 从提高所需的小数位数79来80或者 …

我需要能够在Redis中进行以下操作：

• 当且仅当结果> 0时，才减小n值
• 否则，什么都不做
• 处理任意精度的十进制数字（我需要使用浮点格式）
• 可供其他进程访问

简而言之，这是一个“平衡”：如果我在此字段中有足够的空间，则可以使用它，否则，不可以。有时候，它必须减少很多余额

为此，我制作了一个LUA脚本来计算减量的结果，然后使用该结果修改字段。我选择此解决方案是因为：

• 这是原子的
• 较简单的INCRBYFLOAT不管结果如何都进行减法，并且似乎没有适当的精度
• 使用了LUA库http://oss.digirati.com.br/luabignum/

我面临的问题：

• 使用的lib不适合：它仅适用于整数，并且每次发送都太大（使用evalsha的事件，速度很慢）
• 在Redis =>中编程Lua脚本时如何包含第三方库 =>接下来，我对在Redis上使用附加模块非常困惑。但是，这是从过去到现在。现在怎么样？
• 我不确定是否有更有效的方法来做到这一点？欢迎提供有关代码本身的任何建议
• Redis真的可以满足我的需求吗？

输入“值”的格式如下：Array <{键：字符串，字段：字符串，值：字符串// //实际上是一个BigNumber，具有字符串格式}>

this.redisClient.eval(`
    ${luaBigNumbers}

    local operations = cjson.decode(KEYS[1])
    local isStillValid = true
    local test

    for k, v in pairs(operations) do
      local temp = BigNum.new(redis.call('hget', v.key, v.field))
      local res = BigNum.mt.add(temp, BigNum.new(v.value))

      if BigNum.mt.lt(res, BigNum.new('0')) then
        isStillValid = false
      end
    end

    if isStillValid then
      for k, v in pairs(operations) do
        local temp = BigNum.new(redis.call('hget',v.key, v.field))
        redis.call('hset', v.key, v.field, …

我已经使用GMP库和C++来编写Gauss-Legendre算法的实现来计算pi的数字.

它有正确的输出,但问题是我不知道输出"变坏",因为我必须在代码中指定精度.

以下是使用64位精度的输出:3.141592653589793238*35*,后两位数字不正确.

我的问题是,如果我想ň pi的数字,有多少精度比特b,多少算法的迭代我将需要？

谢谢