任何人都可以为这个插口算法代码Pitiny.c做头或者故事
这个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
时,我正在研究无损压缩算法,但仍然没有运气。
奇怪的是,它成功编译没有错误或错误,但就像我说我不能成为代码的头或者故事,甚至它的语法。 我想知道最近发生了什么? 这究竟是做什么的?
更新
这个程序是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;}
本文的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
- 是一个空的初始化,它也是一个空语句 。
- 从
c
减去14
并将值分配回c
并同时为b
分配相同的值。 该循环将执行2500
次,因为35014/14
是2501并且在第2501
次迭代时结果将为0
并因此为假并且循环将停止。 -
h
被分配printf
的结果,即打印的字符数。 打印出来的是e+d/f
的结果,并且由于格式说明符中的04
,因此总是至少4位数和0填充。
现在我们有一个内部for循环 :
for(e=d%=f;(g=--b*2);d/=g) ^ ^ ^ 1 2 3
- 将
e
和d
初始化为d modulus f
。 - 由于运算符优先级 ,
b
的前递减和倍数乘以2
并将结果赋给g
-
d
除以g
并分配结果。
最后是for for循环的主体:
d=d*b+f*(h?a[b]:f/5), a[b]=d%--g; ^ ^ 1 2
使用1
的条件运算符和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
但之后将永远不再为0
,因为它总是在外部for循环中被赋予非零值,所以除了第一次h
其他值将被赋值a[b]
。
(2)
将再次由于优先级预先递减g
,然后评估d
模数结果并将其分配给a[b]
。
只是为了笑容:
“计算”Pi到10,000位
这是一个“简化”版本。 “简化”意味着使用赋值语句和for循环的结果分解多个运算符。 缺少是有意义的名字。
(这是根据原始代码的结果进行validation的。
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; } }
运行时:
原始时间:1.110
更简单的时间:1.138
当然大部分时间都是格式化和打印。
输出:
它可以写成
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; } } }
换句话说,它是循环的两倍