找回密码
 新注册用户
搜索
楼主: fwjmath

[新闻] 跟yoyo@home合作的新子项目:搜索奇异奇数

[复制链接]
发表于 2013-9-1 09:56:12 | 显示全部楼层
和yoyo的通信好像出了点儿问题……接包送包都不稳定,是我个人的问题吗?
回复

使用道具 举报

发表于 2013-9-1 10:45:54 | 显示全部楼层
看着停眼熟,原来论坛首页的新闻有
2.png

回复

使用道具 举报

发表于 2013-9-1 11:30:31 | 显示全部楼层
您提到,大量地用到了128位整数的运算。请问128bit整数是怎么实现的?用long long还是__int128,还是结构体?
回复

使用道具 举报

 楼主| 发表于 2013-9-1 13:50:16 | 显示全部楼层
wpf999 发表于 2013-9-1 11:30
您提到,大量地用到了128位整数的运算。请问128bit整数是怎么实现的?用long long还是__int128,还是结构体 ...

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

回复

使用道具 举报

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

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

使用道具 举报

 楼主| 发表于 2013-9-1 14:10:28 | 显示全部楼层
wpf999 发表于 2013-9-1 14:00
谢谢。如果排序占用时间较大,可以考虑自己实现排序,记得标准库是快速排序算法,复杂度为O(nlogn)。如 ...

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

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

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

回复

使用道具 举报

发表于 2013-9-1 20:14:52 | 显示全部楼层
好强悍~~~话说移动设备能跑不?
回复

使用道具 举报

发表于 2013-9-1 22:17:33 | 显示全部楼层
抢生意啊
回复

使用道具 举报

发表于 2013-9-1 22:40:27 | 显示全部楼层
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 年后才知道有什么用。

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

使用道具 举报

发表于 2013-9-1 22:59:49 | 显示全部楼层
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 位都可以,这由各个编译器决定,没有统一标准。
回复

使用道具 举报

发表于 2013-9-1 23:15:59 | 显示全部楼层
我要迟一点才能投入资源。现在跑手提太热,家里的电脑又被人占了。。。
回复

使用道具 举报

发表于 2013-9-2 21:36:51 来自手机 | 显示全部楼层
refla 发表于 2013-9-1 22:40
数学研究基本上都没有什么“现实意义”的。比如,计算机硬件的基础是布尔代数,
http://zh.wikipedia.org ...

非常赞同:-D
回复

使用道具 举报

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

求解子集和数的比较快 ?

具体瓶颈在哪?是求解子集,还是对已知的子集求和?
回复

使用道具 举报

 楼主| 发表于 2013-9-3 02:29:08 | 显示全部楼层
refla 发表于 2013-9-2 22:14
求解子集和数的比较快 ?

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

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

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

回复

使用道具 举报

发表于 2013-9-3 09:49:17 | 显示全部楼层
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的约数。

不知道我这个猜想成不成立?
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 新注册用户

本版积分规则

论坛官方淘宝店开业啦~
欢迎大家多多支持基金会~

Archiver|手机版|小黑屋|中国分布式计算总站 ( 沪ICP备05042587号 )

GMT+8, 2024-3-28 19:20

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表