4

这个C程序只有 143 个字符长！

但它会“解压缩”为Pi的前 10,000 位数字。

//  Created by cheeseMan on 30/11/13.

long a[35014],b,c=35014,d,e,f=1e4,g,h;

int main(int argc, const char * argv[])

{
    for(;(b=c-=14);

        h=printf("%04ld",e+d/f))

        for(e=d%=f;(g=--b*2);d/=g)
            d=d*b+f*(h?a[b]:f/5), a[b]=d%--g;
}

当我遇到这个时，我正在对无损压缩算法进行一些研究，但仍然没有运气pitiny.c。

奇怪的是它编译成功，没有错误或错误，但就像我说的那样，我无法对代码做出头脑或故事，甚至它的语法。我只是想知道这是怎么回事？它到底在做什么？

4

3 回答 3

11

更新

该程序是Pi - Unleashed一书中Pi的数字的插口算法的故意混淆实现，我们可以在该书的第 37 页找到原始版本，如下所示：

a[52514],b,c=52514,d,e,f=1e4,g,h;main(){for(;b=c-=14;h=printf("%04d", e+d/ f))for(e=d%=f;g=--b*2;d/=g)d=d b+f (h?a[b]:f/5),a[b]=d ％ - G;}

论文Unbounded Spigot Algorithms for the Digits of Pi在解释算法方面做得很好。基本上它是这个扩展的一个实现：

公式

原来的

除了让代码无法理解和给人们留下深刻印象之外，它被设计成这种方式的原因让我无法理解，但我们可以分解正在发生的事情，首先在这里：

long a[35014],b,c=35014,d,e,f=1e4,g,h;

变量是静态的，因为它们是全局的，因此所有未显式初始化的变量都将初始化为0. 接下来我们有一个外部for 循环：

for(;(b=c-=14); h=printf("%04ld",e+d/f)
    ^ ^         ^
    1 2         3
  1. 是一个空初始化，它也是一个空语句。
  2. 减去并将值重新分配14给，并将相同的值分配给。该循环将执行时间，因为是 2501，并且在第th 次迭代中，结果将因此为false，并且循环将停止。ccb250035014/1425010
  3. h正在分配其结果printf是打印的字符数。打印出来的是格式说明符中的结果，并且总是e+d/f至少有 4 位数字和零填充。04

现在我们有一个内部for 循环：

for(e=d%=f;(g=--b*2);d/=g)
    ^       ^        ^
    1       2        3
  1. 初始化e和。d_d modulus f
  2. 由于运算符的优先级，预先递减b和倍增，并将2结果分配给g
  3. d正在被除以g并分配结果。

最后是内部 for 循环的主体：

d=d*b+f*(h?a[b]:f/5), a[b]=d%--g;
          ^         ^
          1         2

使用条件运算符in1和逗号运算符in 2。所以我们至少可以把它分成：

d    = d*b+f*(h?a[b]:f/5) ; // (1)
a[b] = d%--g;               // (2)

(1)可以进一步细分为：

long tmp =  h ? a[b] : f/5 ;  // conditional operator
d = (d * b) + f * tmp;

条件运算符仅在第一次迭代期间很重要，因为它h被初始化为0但以后永远不会再次出现，因为它总是在外部for 循环0中分配一个非零值，所以除了第一次之外将被分配。ha[b]

(2)将再次由于优先级预先递减g，然后计算d模数并将其分配给a[b].

于 2013-11-29T14:30:55.150 回答
2

Just for grins:
"Calculate" Pi to 10,000 digits
Here is a "simplified" version. "Simplified" meaning breaking up the multiple operators, using the results of assignment statements and for loops. Missing are meaningful names.

(this was verified against the results of the original code.

void simplier() {
    long a[35014];
    long b = 0;
    long c = 35000;
    long d = 0;
    long e = 0;
    long f = 10000;
    long g = 0;
    long h = 0;
    long i = 0;

    while (c) {
        d %= f;
        e  = d;
        b  = c-1;
        g  = b*2;

        while(g) {
            g -= 1;
            i  = h ? a[b] : f/5;
            d  = (d*b) + (f*i);
            a[b] = d % g;
            d /= g;
            b -= 1;
            g  = b*2;
        }

        printf("%04ld", e+d/f);
        h  = 1;
        c -= 14;
    }
}

Runtimes:

Original time: 1.110
Simplier time: 1.138

Of course most of the time is in the formatting and printing.

Output:

3141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105559644622948954930381964428810975665933446128475648233786783165271201909145648566923460348610454326648213393607260249141273724587006606315588174881520920962829254091715364367892590360011330530548820466521384146951941511609433057270365759591953092186117381932611793105118548074462379962749567351885752724891227938183011949129833673362440656643086021394946395224737190702179860943702770539217176293176752384674818467669405132000568127145263560827785771342757789609173637178721468440901224953430146549585371050792279689258923542019956112129021960864034418159813629774771309960518707211349999998372978049951059731732816096318595024459455346908302642522308253344685035261931188171010003137838752886587533208381420617177669147303598253490428755468731159562863882353787593751957781857780532171226806613001927876611195909216420198938095257201065485863278865936153381827968230301952035301852968995773622599413891249721775283479131515574857242454150695950829533116861727855889075098381754637464939319255060400927701671139009848824012858361603563707660104710181942955596198946767837449448255379774726847104047534646208046684259069491293313677028989152104752162056966024058038150193511253382430035587640247496473263914199272604269922796782354781636009341721641219924586315030286182974555706749838505494588586926995690927210797509302955321165344987202755960236480665499119881834797753566369807426542527862551818417574672890977772793800081647060016145249192173217214772350141441973568548161361157352552133475741849468438523323907394143334547762416862518983569485562099219222184272550254256887671790494601653466804988627232791786085784383827967976681454100953883786360950680064225125205117392984896084128488626945604241965285022210661186306744278622039194945047123713786960956364371917287467764657573962413890865832645995813390478027590099465764078951269468398352595709825822620522489407726719478268482601476990902640136394437455305068203496252451749399651431429809190659250937221696461515709858387410597885959772975498930161753928468138268683868942774155991855925245953959431049972524680845987273644695848653836736222626099124608051243884390451244136549762780797715691435997700129616089441694868555848406353422072225828488648158456028506016842739452267467678895252138522549954666727823986456596116354886230577456498035593634568174324112515076069479451096596094025228879710893145669136867228748940560101503308617928680920874760917824938589009714909675985261365549781893129784821682998948722658804857564014270477555132379641451523746234364542858444795265867821051141354735739523113427166102135969536231442952484937187110145765403590279934403742007310578539062198387447808478489683321445713868751943506430218453191048481005370614680674919278191197939952061419663428754440643745123718192179998391015919561814675142691239748940907186494231961567945208095146550225231603881930142093762137855956638937787083039069792077346722182562599661501421503068038447734549202605414665925201497442850732518666002132434088190710486331734649651453905796268561005508106658796998163574736384052571459102897064140110971206280439039759515677157700420337869936007230558763176359421873125147120532928191826186125867321579198414848829164470609575270695722091756711672291098169091528017350671274858322287183520935396572512108357915136988209144421006751033467110314126711136990865851639831501970165151168517143765761835155650884909989859982387345528331635507647918535893226185489632132933089857064204675259070915481416549859461637180270981994309924488957571282890592323326097299712084433573265489382391193259746366730583604142813883032038249037589852437441702913276561809377344403070746921120191302033038019762110110044929321516084244485963766983895228684783123552658213144957685726243344189303968642624341077322697802807318915441101044682325271620105265227211166039666557309254711055785376346682065310989652691862056476931257058635662018558100729360659876486117910453348850346113657686753249441668039626579787718556084552965412665408530614344431858676975145661406800700237877659134401712749470420562230538994561314071127000407854733269939081454664645880797270826683063432858785698305235808933065757406795457163775254202114955761581400250126228594130216471550979259230990796547376125517656751357517829666454779174501129961489030463994713296210734043751895735961458901938971311179042978285647503203198691514028708085990480109412147221317947647772622414254854540332157185306142288137585043063321751829798662237172159160771669254748738986654949450114654062843366393790039769265672146385306736096571209180763832716641627488880078692560290228472104031721186082041900042296617119637792133757511495950156604963186294726547364252308177036751590673502350728354056704038674351362222477158915049530984448933309634087807693259939780541934144737744184263129860809988868741326047215695162396586457302163159819319516735381297416772947867242292465436680098067692823828068996400482435403701416314965897940924323789690706977942236250822168895738379862300159377647165122893578601588161755782973523344604281512627203734314653197777416031990665541876397929334419521541341899485444734567383162499341913181480927777103863877343177207545654532207770921201905166096280490926360197598828161332316663652861932668633606273567630354477628035045077723554710585954870279081435624014517180624643626794561275318134078330336254232783944975382437205835311477119926063813346776879695970309833913077109870408591337464144282277263465947047458784778720192771528073176790770715721344473060570073349243693113835049316312840425121925651798069411352801314701304781643788518529092854520116583934196562134914341595625865865570552690496520985803385072242648293972858478316305777756068887644624824685792603953527734803048029005876075825104747091643961362676044925627420420832085661190625454337213153595845068772460290161876679524061634252257719542916299193064553779914037340432875262888963995879475729174642635745525407909145135711136941091193932519107602082520261879853188770584297259167781314969900901921169717372784768472686084900337702424291651300500516832336435038951702989392233451722013812806965011784408745196012122859937162313017114448464090389064495444006198690754851602632750529834918740786680881833851022833450850486082503930213321971551843063545500766828294930413776552793975175461395398468339363830474611996653858153842056853386218672523340283087112328278921250771262946322956398989893582116745627010218356462201349671518819097303811980049734072396103685406643193950979019069963955245300545058068550195673022921913933918568034490398205955100226353536192041994745538593810234395544959778377902374216172711172364343543947822181852862408514006660443325888569867054315470696574745855033232334210730154594051655379068662733379958511562578432298827372319898757141595781119635833005940873068121602876496286744604774649159950549737425626901049037781986835938146574126804925648798556145372347867330390468838343634655379498641927056387293174872332083760112302991136793862708943879936201629515413371424892830722012690147546684765357616477379467520049075715552781965362132392640616013635815590742202020318727760527721900556148425551879253034351398442532234157623361064250639049750086562710953591946589751413103482276930624743536325691607815478181152843667957061108615331504452127473924544945423682886061340841486377670096120715124914043027253860764823634143346235189757664521641376796903149501910857598442391986291642193994907236234646844117394032659184044378051333894525742399508296591228508555821572503107125701266830240292952522011872676756220415420516184163484756516999811614101002996078386909291603028840026910414079288621507842451670908700069928212066041837180653556725253256753286129104248776182582976515795984703562226293486003415872298053498965022629174878820273420922224533985626476691490556284250391275771028402799806636582548892648802545661017296702664076559042909945681506526530537182941270336931378517860904070866711496558343434769338578171138645587367812301458768712660348913909562009939361031029161615288138437909904231747336394804575931493140529763475748119356709110137751721008031559024853090669203767192203322909433467685142214477379393751703443661991040337511173547191855046449026365512816228824462575916333039107225383742182140883508657391771509682887478265699599574490661758344137522397096834080053559849175417381883999446974867626551658276584835884531427756879002909517028352971634456212964043523117600665101241200659755851276178583829204197484423608007193045761893234922927965019875187212726750798125547095890455635792122103334669749923563025494780249011419521238281530911407907386025152274299581807247162591668545133312394804947079119153267343028244186041426363954800044800267049624820179289647669758318327131425170296923488962766844032326092752496035799646925650493681836090032380929345958897069536534940603402166544375589004563288225054525564056448246515187547119621844396582533754388569094113031509526179378002974120766514793942590298969594699556576121865619673378623625612521632086286922210327488921865436480229678070576561514463204692790682120738837781423356282360896320806822246801224826117718589638140918390367367222088832151375560037279839400415297002878307667094447456013455641725437090697939612257142989467154357846878861444581231459357198492252847160504922124247014121478057345510500801908699603302763478708108175450119307141223390866393833952942578690507643100638351983438934159613185434754649556978103829309716465143840700707360411237359984345225161050702705623526601276484830840761183013052793205427462865403603674532865105706587488225698157936789766974220575059683440869735020141020672358502007245225632651341055924019027421624843914035998953539459094407046912091409387001264560016237428802109276457931065792295524988727584610126483699989225695968815920560010165525637567

于 2013-11-29T17:51:12.750 回答
2

它可以写成

long a[35014];
long b;
long c=35014;
long d;
long e;
long f=1e4;
long g;
long h;

int main(int argc, const char * argv[])
{
    for(; (b=c-=14); h=printf("%04ld",e+d/f)) {
        for(e=d%=f; (g=--b*2); d/=g) {
            d = (d * b) + f * ( h ? a[b] : f/5);
            a[b] = d % --g;
        }
    }
}

换句话说，它是双for循环

于 2013-11-29T14:12:00.040 回答