跟yoyo@home合作的新子项目：搜索奇异奇数

nekoko

和yoyo的通信好像出了点儿问题……接包送包都不稳定，是我个人的问题吗？

zhouxiaobo

看着停眼熟，原来论坛首页的新闻有

wpf999

您提到，大量地用到了128位整数的运算。请问128bit整数是怎么实现的？用long long还是__int128，还是结构体？

fwjmath

wpf999 发表于 2013-9-1 11:30
您提到，大量地用到了128位整数的运算。请问128bit整数是怎么实现的？用long long还是__int128，还是结构体 ...

用的是__int128。long long的话只有64位。其实写结构体也可以，但如果考虑效率，要内嵌汇编，而且因为程序里大量使用了标准库的排序（排序可能占了一半的时间），如果用结构体的话，编译器编译出的结果大概也不如原生支持的__int128。所以我选择了__int128。

wpf999

fwjmath 发表于 2013-9-1 13:50
用的是__int128。long long的话只有64位。其实写结构体也可以，但如果考虑效率，要内嵌汇编，而且因为程 ...

谢谢。如果排序占用时间较大，可以考虑自己实现排序，记得标准库是快速排序算法，复杂度为O（nlogn）。如果用桶排序，复杂度为O（n），效率更高，可以考虑使用。

fwjmath

wpf999 发表于 2013-9-1 14:00
谢谢。如果排序占用时间较大，可以考虑自己实现排序，记得标准库是快速排序算法，复杂度为O（nlogn）。如 ...

因为排序的元素其实不太多，大概1000个左右，桶排序需要元素个数比较大的时候才会占优势，所以才选择了标准库的排序。

其实主要花时间的有两个部分，一个是排序，另一个是递归求解子集和数问题。随着计算的数增大，第二部分的权重也会增大。但是具体是多少的话，还要详细看profiling。

关于子集和数的部分，因为总和很大，那种动态规划的方法行不通，所以才采用的递归求解。如果有求解子集和数的比较快的算法的话，可能对程序本身更加有帮助。目前我自己是找不到，如果知道的话请务必告诉我一声~~~

lydy1993

好强悍~~~话说移动设备能跑不？

refla

抢生意啊

refla

Stella 发表于 2013-8-31 10:24
能否简单描述一下研究奇异数的价值？对什么方向的研究有所帮助？简单的搜索了一下，没有查到太多的资料。谢 ...

数学研究基本上都没有什么“现实意义”的。比如，计算机硬件的基础是布尔代数，
http://zh.wikipedia.org/wiki/%E5%B8%83%E5%B0%94%E4%BB%A3%E6%95%B0

见“历史”一节，诞生于 19 世纪 40 年代，而第一台电子计算机则在 100 年后的 20 世纪 40 年代才出现。

还有，这两年的机器学习很火，据说是因为发现 100 年前的一个公式“很有用”。而在此前，这个公式躺在文献库里一个世纪，无人问津。

所以，数学作为一门理论学科，至少要经过 100 年后才知道有什么用。

但如果大家都想着“现在有什么用”，那数学永远也不会发展了，人类社会也就永远停留在此刻了。

refla

fwjmath 发表于 2013-9-1 13:50
用的是__int128。long long的话只有64位。其实写结构体也可以，但如果考虑效率，要内嵌汇编，而且因为程 ...

确切地说，long long 在 C/C++ 标准只规定了“位数不比 long 少”，long 则是“位数不比 int 少”，int 则是机器中的“自然数”，即执行效率最高的字长。

比如，32 位系统（硬件和操作系统都支持 32 位）中，int 的字长就是 32 位。而 long / long long 则 32、64 位，甚至 128 位都可以，这由各个编译器决定，没有统一标准。

refla

我要迟一点才能投入资源。现在跑手提太热，家里的电脑又被人占了。。。

超哥不郁闷

refla 发表于 2013-9-1 22:40
数学研究基本上都没有什么“现实意义”的。比如，计算机硬件的基础是布尔代数，
http://zh.wikipedia.org ...

非常赞同:-D

refla

fwjmath 发表于 2013-9-1 14:10
因为排序的元素其实不太多，大概1000个左右，桶排序需要元素个数比较大的时候才会占优势，所以才选择了标 ...

求解子集和数的比较快 ？

具体瓶颈在哪？是求解子集，还是对已知的子集求和？

fwjmath

refla 发表于 2013-9-2 22:14
求解子集和数的比较快 ？

具体瓶颈在哪？是求解子集，还是对已知的子集求和？ ...

就是要求解子集和数问题啊，检查一个数N是不是奇异数，就相当于先构造N的真子集组成的集合，然后再以N为目标解子集和数问题。

参见：http://zh.wikipedia.org/wiki/%E5 ... D%E5%95%8F%E9%A1%8C

refla

fwjmath 发表于 2013-9-3 02:29
就是要求解子集和数问题啊，检查一个数N是不是奇异数，就相当于先构造N的真子集组成的集合，然后再以N为 ...

这个问题我没问清楚。

求解子集元素的总和，我也搞过。我当时的想法是这样的：

以 N=100 为例，其全体约数的集合为{1, 2, 4, 5, 10, 20, 25, 50}，则

1+2+4+5+10+20+25=67<100
1+2+4+5+10+20+25+50=117>100

由此可以断定，只有从元素 50 开始的子集，比如{1, 2, 4, 50}，才有可能满足要求。因此，前面的子集，比如{1, 2, 4}就直接跳过。

尽管跳过了一些搜索区间，但搜索速度还是非常缓慢。搜索 43 个元素构成的整个组合区间，我花了两周的时间（E3210，24小时不停机）。

我生成组合的算法是经典的“字典法”，即 101 的下一个组合是 110。我想可能是这个算法太低效了。

所以，我想问的是：

① 你的子集生成算法是什么？
② 你认为你整个算法中，瓶颈是在子集生成？128bits 求和？还是两者都有？

谢谢！

另外，我还想补充一个问题。

对于找约数，我有一种感觉：如果约数的平方小于原数，则可能存在比它大的“真约数”。

还是以 100 为例，原数N=100，约数n=5时，5^2=25<100；约数n=10时，10^2=100，而 10 可以分解成 2 和 5 两个约数，故 10 不是“真约数”，但 5 是“真约数”。

好了，剩下的约数我可以不用找了，直接用真约数去“凑”就可以了。比如，5^2=25也是一个100的约数。

不知道我这个猜想成不成立？