草庐IT

c++ - 指数导致的总和

coder 2024-02-03 原文

我正在做一个练习，似乎对如何从数学上而不是从句法上解决问题更加执着。

当数量相对较小时，想法很简单。给定一个底数和幂，该程序应将结果的位数相加。让我们用一个例子来解释我想做什么。
base 2 and power 8给出了，因此2^8 = 256，然后程序应将答案的位数相加，这样
整个过程就是2+5+6 = 13，它求底数乘幂的结果的位数之和。

现在，这是一个简单的示例，如果我移动到一个荒谬的巨大数字(例如2 ^ 1000)，由于结果巨大且会被截断，这几乎不可能只丢掉我尝试过的任何东西，因为我们会失去精度。答案必须是准确的。

我认为也许有一种数学方法可以不同地执行此操作，以某种方式将其分解为较小的块，但除了以下内容，我真的无法想到其他任何关系:
2^1000 = 2^500*2^5001000 log(2) = log(ans)
无论哪种方式，这都无法使我接近数字，因此我可以开始求和。

我希望我能清楚地解释它。

对于它的值(value)，我正在使用C++(也给了lua一招)，也许我可以使用一个库，但是这个数字将有302位数字，我应该编写程序来处理1000的指数。我真的认为我在这里缺少一些数学技巧。

找到了EDIT部分解决方案

我今天在lua上花了一些时间来尝试解决这个问题，今晚我将用C++试一试，看看是否得到不同的结果。我可以找到错误的根源，但是我找到了适用于大多数情况的解决方案。只是不是2 ^ 1000，以及其他一些指数非常大的指数。

该解决方案的工作原理和MooseBoys的评论均已描述。

我利用了模幂。 lua代码如下:

-- Function purpose:  Calculate modular exponent (see wiki in comment 
from MooseBoys)
--
-- @param b: base
-- @param e: exponent
-- @param m: modulation
-- @result c: result
-- 
--  example: 2^15    = 32768
--  ModPow(2,15,10)  = 8
--  ModPow(2,15,100) = 68
--
local ModPow = function(b,e,m)
   local c = 1

   for i = 1, e do
       c = c*b%m
   end

   return c
end

-- Function purpose: Check uniqueness of result from last one.
-- ModPow will not return leading 0, so in the case 2^20 = 1048576
-- Sum result would equal 35 because:
-- ModPow(2,20,10^5) = 48576
-- ModPow(2,20,10^6) = 48576  
-- 
-- Also there is an issue with rounding I am working on.  Current Problem
-- Sometimes, result is          6.xxxxxxxxxx2e+294
-- and with leading 0 result is  6.xxxxxxxxxx3e+294  
-- So the result does not catch there was a leading 0 since s1 and s2 
-- are not equal
-- However, this fix is giving me problems (assuming mod exponent always 
-- grows by an order of magnitude.. 10^(n+1) each cycle), I assumed 
-- just checking exponent value is good enough
-- Now I get some strange results as outlined blow    
-- 
-- @param s1: Current result from ModPow (as string)
-- @param s2: Last result of ModPow (as string)
-- @result bool based on whether or not this number is valid to add to the sum 
local CheckUnique = function(s1,s2)  

   if s1:find('e') and s2:find('e') then   --fix rounding?
      if(s1:sub(s1:find('e'),s1:len())==s2:sub(s2:find('e'),s2:len())) then print(0) return false end
   elseif (s1 == s2) then print(0) return false  --fix leading 0
   end

   print(s1) --test
   return true
end


--self explanitory
local base = 2
local exp = 1000
local mod = 10

--Counters and value holders
local sum = 0
local lval = 0
local val,valS = 1,'1'
local cycle = 1


--Know when to stop
local endval = base^exp
print(endval)

while val ~= endval do

   val = ModPow(base,exp,mod^cycle)      
   valS = tostring(val)

   if(CheckUnique(valS,lval)) then         --is unique   
       sum = sum + tonumber(valS:sub(1,1)) --sum leading digit    
   end

   lval = valS
   cycle = cycle+1

end

print(sum)

问题出在结果之内。
您可以想象，从mod周期打印每个结果应该是这样的
Value: 1048576
6
76
576
8576
48576
0
1048576
sum: 31

当检查检测到前导0时，我会在上面放一个print(0)，否则打印c的值。您会看到，每个第一个数字将被加起来以给出正确的总和。每行净线都应包含前一行和新数字，就像基本上是一个不断增长的标题一样。

但是，现在我无法解决的问题是将其扩展为大量时，可以说是我要寻求的解决方案。 2 ^ 1000 ..

结果:(健康线，接近尾声)
2.6725480652012e+288
6.2672548065201e+289
8.6267366100831e+290
1.8626730674387e+291
7.186267401715e+292
0
6.0718626734093e+294
8.6071862673409e+295
0
5.0860718626736e+297
1.5086071862673e+298
7.1508607186267e+299

例如，最后一行与您在列表中列出倒数第一位数字相同:7.1508607186267e+2997 15086071862
我很兴奋，发现答案不正确。我深入研究了这些线，发现了这些不健康的线:
9.18229858679e+069
7.5447775000848e+070
8.8906306939456e+069
4.1746958410049e+072
5.0621122825342e+073
4.1602034907325e+074
1.9248790609684e+075 -- no such order 454879 but have 924879?
....
8.3104764719996e+086
3.8310476472e+087
4.6735451839797e+088
8.0281504870817e+089
3.0808317990698e+090
9.0430240225156e+091 --no such order 938438...?

似乎有几个地方会发生这种情况，并且仅对超过200ish的指数有效。我检查了100，结果非常理想。注意到200中的错误，例如
2.9937827928353e+018
0
2.0299378279284e+020
2.2029937827928e+021
7.8493010541604e+022
5.0206666406882e+023
0
3.384239167984e+025

任何人都有新的提示，可能是什么问题？
(对不起，我的lua插入者可能有所不同，一般来说不确定lua。
我只是在使用用于游戏脚本的IDE)

好的，靠近一点。我的C++程序可以更好地处理事情，这是代码。仍然得到错误的答案，但至少我得到的位数相同。我现在似乎无法弄清楚这有什么问题。问题是，此练习是在网站上，我不知道正确的答案，只是我的程序给我2 ^ 1000的错误答案。它通过了我提供的其他测试用例(我可以手动做的测试用例，最多可以检查答案2 ^ 20)
#include <iostream>
#include <cmath>


double ModPow(int,int,long double);

int main() {


    int base = 2;
    int power = 1000;
    long double mod = 10;
    long double val = 0;
    int i = 0;
    int sum = 0;

    double ans = pow(base,power);
    std::cout << ans << std::endl;





    while(ans != val) {

        val = ModPow(base,power,mod);
        std::cout<< val << "   ";
        sum += int(floor(val/(mod/10)));
        mod = mod * 10;
        i += 1;
        if(i%5 == 0) std::cout << std::endl;

    }

    std::cout << std::endl << sum << std::endl;
    std::cout << i << std::endl;



    std::cin.ignore();
    return 0;

}


double ModPow(int b, int e, long double m) {

    double c = 1;

    for(int i = 1; i <= e; i++) {
        c = fmod(c*b,m);
    }


    return c;
}

在这里，我可以看到在循环期间仍然有奇怪的行为。从逻辑上讲，随着我不断添加数字，exp应该每次增加一。我在e + 22处看到了行为，然后回落到e + 21，不知道为什么。这是我程序的完整结果(我制作了 double 长 double ，并添加了文件写入功能，但结果与上面的代码相同)
6   76   376   9376   69376   
69376   8.06938e+006   6.80694e+007   6.68069e+008   5.66807e+009   
5.66807e+009   2.05668e+011   7.20567e+012   3.72057e+013   8.37206e+014   
6.83721e+015   8.68372e+016   3.86837e+017   4.38684e+018   2.43868e+019   
6.24387e+020   2.62439e+021   8.81371e+022   7.17853e+021   6.67056e+024   
5.66706e+025   2.56671e+026   6.11305e+027   1.49872e+026   7.84562e+029   
8.79213e+030   5.26226e+031   2.66375e+032   7.26638e+033   4.84075e+034   
3.21959e+035   6.35788e+036   6.73897e+037   6.73897e+037   6.73897e+037   
2.62589e+038   2.98945e+041   2.98945e+041   6.02989e+043   9.17698e+044   
7.16921e+045   7.05229e+046   6.70523e+047   6.5113e+048   4.65113e+049   
8.52121e+050   3.85212e+051   7.38521e+052   4.19563e+053   5.91881e+054   
4.39205e+055   3.9345e+056   9.04097e+057   9.04097e+057   3.68596e+059   
1.49612e+060   7.7534e+061   7.39705e+061   4.22204e+063   6.98596e+063   
6.92886e+065   4.69289e+066   8.22986e+067   1.82299e+068   9.1823e+069   
7.54478e+070   1.14456e+071   4.11446e+072   3.62523e+073   9.90302e+074   
1.92488e+075   4.59175e+076   5.88549e+077   1.35968e+078   6.13597e+079   
6.6136e+080   4.66136e+081   7.48063e+082   6.12132e+083   8.8392e+084   
7.86463e+085   6.94822e+086   6.32933e+087   5.62433e+088   6.56243e+089   
2.3548e+090   5.60251e+090   7.14338e+091   9.90736e+093   6.14551e+094   
5.791e+095   2.5791e+096   5.12015e+097   1.81734e+098   3.08347e+099   
4.30835e+100   4.43083e+101   9.44308e+102   8.62251e+103   4.79117e+104   
4.47912e+105   4.70365e+106   6.26271e+107   9.63625e+108   1.34535e+109   
2.5938e+110   4.77635e+110   7.92388e+112   2.33449e+113   9.38763e+114   
1.74483e+115   4.23631e+116   3.8324e+117   3.10928e+118   8.8341e+119   
9.80234e+120   5.28235e+121   4.52823e+122   8.69571e+123   7.59308e+124   
6.61087e+123   8.34403e+126   8.26135e+127   3.82614e+128   6.83699e+128   
5.48343e+130   7.05731e+131   2.02676e+132   1.20268e+133   3.72264e+134   
4.37226e+135   5.43723e+136   1.68563e+137   9.63719e+138   3.70399e+139   
1.84462e+140   6.61036e+141   4.66104e+142   3.85213e+143   2.38521e+144   
7.39926e+145   4.95209e+146   2.70772e+147   1.27077e+148   9.49987e+149   
6.39539e+150   9.72139e+151   5.89019e+152   7.15679e+153   7.15679e+153   
3.38172e+154   5.84268e+156   9.72579e+157   4.87575e+158   5.6501e+159   
1.85286e+160   4.18529e+161   4.60739e+162   7.12977e+163   5.71298e+164   
8.86201e+165   7.8862e+166   5.82415e+167   4.61194e+168   8.46119e+169   
7.95321e+170   9.01956e+171   7.90196e+172   1.40488e+173   2.38969e+174   
9.12607e+175   8.5208e+176   2.61635e+177   7.26163e+178   1.87538e+179   
6.18754e+180   6.6906e+181   2.05665e+182   3.79061e+183   4.37906e+184   
4.43791e+185   9.87813e+186   1.98781e+187   7.03446e+188   1.57091e+189   
5.7816e+190   7.57816e+191   2.1734e+191   3.5815e+193   9.77689e+194   
8.97769e+195   1.08115e+196   5.10812e+197   4.6079e+198   4.46079e+199   
5.44608e+200   3.69583e+201   3.36958e+202   1.94715e+203   9.19309e+204   
1.7556e+205   9.45675e+206   5.94568e+207   6.45002e+208   9.11561e+209   
1.17058e+210   8.60292e+211   7.86029e+212   2.48236e+213   1.2582e+214   
6.04576e+215   9.60458e+216   4.34447e+217   5.43445e+218   8.42133e+219   
9.84213e+220   1.8562e+221   8.38891e+221   1.08389e+223   7.01599e+223   
1.07016e+225   3.10702e+226   4.3107e+227   1.50548e+228   1.06711e+229   
8.65791e+230   9.86579e+231   8.18076e+232   2.68057e+232   1.85488e+234   
1.85488e+234   2.26339e+236   4.66336e+237   6.27494e+238   5.24964e+239   
3.52496e+240   2.99353e+240   9.96218e+242   8.99622e+243   4.9693e+243   
1.33007e+245   3.78439e+246   1.99925e+247   8.51404e+248   8.47445e+249   
2.95141e+250   7.13201e+251   1.7132e+252   9.76862e+253   9.36726e+254   
3.92421e+255   6.39242e+256   8.42555e+256   4.87969e+258   4.09894e+259   
2.17963e+260   1.61217e+261   8.27277e+261   4.08273e+263   4.53756e+264   
9.67271e+265   9.67271e+265   9.19793e+267   1.91979e+268   2.52109e+267   
5.12996e+270   6.60659e+271   9.64583e+272   6.96458e+273   3.07557e+274   
7.59723e+275   4.30703e+276   6.07449e+277   2.87595e+278   5.82907e+279   
4.59589e+279   2.07609e+281   6.20761e+282   9.17199e+283   5.9172e+284   
5.9172e+284   7.05917e+286   6.70229e+287   2.67023e+288   6.26707e+289   
8.62671e+290   1.86267e+291   7.18627e+292   7.18627e+292   6.07186e+294   
8.60719e+295   8.60719e+295   5.08607e+297   1.50861e+298   7.15086e+299   
7.15086e+299   1.07151e+301

最佳答案

您想要一个不直接涉及做2**1000的解决方案吗？好吧，我们可以手动完成。 2**1000有多少位数？绝对最多为1,000。

因此:

int sum_digits(int e) {
    std::vector<int> digits(e);
    digits[0] = 1;
    int last_digit = 1;

    for (int power = 0; power < e; ++power) {
        int carry = 0;
        for (int idx = 0; idx < last_digit; ++idx) {
            int prod = digits[idx] * 2 + carry;
            if (prod > 9) {
                carry = 1;
                prod -= 10;
            }
            else {
                carry = 0;
            }
            digits[idx] = prod;
        }

        if (carry) {
            digits[last_digit++] = 1;
        }
    }

    // then just sum 'em  
    return std::accumulate(digits.begin(), digits.end(), 0);
}

这相当快，而且显然是正确的。当然，big-Oh时间并不长，但是对于1000、10k和100k coliru的幂，我的答案是0.4ms，28ms和2.8s。小学数学还不错吗？

关于c++ - 指数导致的总和，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28056481/

amp43codebrModPowc++algorithmmathlua

有关c++ - 指数导致的总和的更多相关文章

  1. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  2. ruby - 使用 `+=` 和 `send` 方法 - 2

    如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:

  3. ruby - 如何计算 Liquid 中的变量 +1 - 2

    我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。 最佳答案 因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我

  4. Ruby 守护进程导致 ActiveRecord 记录器 IOError - 2

    我目前正在用Ruby编写一个项目，它使用ActiveRecordgem进行数据库交互，我正在尝试使用ActiveRecord::Base.logger记录所有数据库事件具有以下代码的属性ActiveRecord::Base.logger=Logger.new(File.open('logs/database.log','a'))这适用于迁移等(出于某种原因似乎需要启用日志记录，因为它在禁用时会出现NilClass错误)但是当我尝试运行包含调用ActiveRecord对象的线程守护程序的项目时脚本失败并出现以下错误/System/Library/Frameworks/Ruby.frame

  5. ruby - 从另一个私有(private)方法中使用 self.xxx() 调用私有(private)方法 xxx，导致错误 "private method ` xxx' called” - 2

    我正在尝试获得良好的Ruby编码风格。为防止意外调用具有相同名称的局部变量，我总是在适当的地方使用self.。但是现在我偶然发现了这个:classMyClass上面的代码导致错误privatemethodsanitize_namecalled但是当删除self.并仅使用sanitize_name时，它会起作用。这是为什么？ 最佳答案 发生这种情况是因为无法使用显式接收器调用私有(private)方法，并且说self.sanitize_name是显式指定应该接收sanitize_name的对象(self)，而不是依赖于隐式接收器(也是

  6. arrays - Ruby 数组 += vs 推送 - 2

    我有一个数组数组，想将元素附加到子数组。+=做我想做的，但我想了解为什么push不做。我期望的行为(并与+=一起工作):b=Array.new(3,[])b[0]+=["apple"]b[1]+=["orange"]b[2]+=["frog"]b=>[["苹果"],["橙子"],["Frog"]]通过推送，我将推送的元素附加到每个子数组(为什么？):a=Array.new(3,[])a[0].push("apple")a[1].push("orange")a[2].push("frog")a=>[[“苹果”、“橙子”、“Frog”]、[“苹果”、“橙子”、“Frog”]、[“苹果”、“

  7. += 的 Ruby 方法 - 2

    有没有办法让Ruby能够做这样的事情？classPlane@moved=0@x=0defx+=(v)#thisiserror@x+=v@moved+=1enddefto_s"moved#{@moved}times,currentxis#{@x}"endendplane=Plane.newplane.x+=5plane.x+=10putsplane.to_s#moved2times,currentxis15 最佳答案 您不能在Ruby中覆盖复合赋值运算符。任务在内部处理。您应该覆盖+，而不是+=。plane.a+=b与plane.a=

  8. ruby - 为什么 return 关键字会导致我的 'if block' 出现问题？ - 2

    下面的代码工作正常:person={:a=>:A,:b=>:B,:c=>:C}berson={:a=>:A1,:b=>:B1,:c=>:C1}kerson=person.merge(berson)do|key,oldv,newv|ifkey==:aoldvelsifkey==:bnewvelsekeyendendputskerson.inspect但是如果我在“ifblock”中添加return，我会得到一个错误:person={:a=>:A,:b=>:B,:c=>:C}berson={:a=>:A1,:b=>:B1,:c=>:C1}kerson=person.merge(berson

  9. ruby - Sinatra + Heroku + Datamapper 使用 dm-sqlite-adapter 部署问题 - 2

    出于某种原因，heroku尝试要求dm-sqlite-adapter，即使它应该在这里使用Postgres。请注意，这发生在我打开任何URL时-而不是在gitpush本身期间。我构建了一个默认的Facebook应用程序。gem文件:source:gemcuttergem"foreman"gem"sinatra"gem"mogli"gem"json"gem"httparty"gem"thin"gem"data_mapper"gem"heroku"group:productiondogem"pg"gem"dm-postgres-adapter"endgroup:development,:t

  10. ruby-on-rails - 什么会导致与 APNS 的连接间歇性断开连接？ - 2

    我有一个ruby​​脚本可以打开与Apple推送服务器的连接并发送所有待处理的通知。我看不出任何原因，但当Apple断开我的脚本时，我遇到了管道损坏错误。我已经编写了我的脚本来适应这种情况，但我宁愿只是找出它发生的原因，这样我就可以在第一时间避免它。它不会始终根据特定通知断开连接。它不会以特定的字节传输大小断开连接。一切似乎都是零星的。您可以在单个连接上发送的数据传输或有效负载计数是否有某些限制？看到人们的解决方案始终保持一个连接打开，我认为这不是问题所在。我看到连接在3次通知后断开，我看到它在14次通知后断开。我从未见过它能超过14点。有没有人遇到过这种类型的问题？如何处理？

随机推荐