随笔:9 文章:0 评论:0 引用:0
C++博客 首页 发新随笔
发新文章 联系 聚合管理

2009年8月26日

我承认,这个是水帖....

在绕了半个中国后,终于回到了可爱的南京................

顺便祝大家节日快乐



                     2009年7月初7
posted @ 2009-08-26 15:53 pterosaur 阅读(101) | 评论 (0)编辑 收藏

2009年6月30日

     摘要: 登记一个表格,和程序没啥关系,不相关的请忽略.权当冒泡.同轴电缆接头特性:  Connector Name Frequency Range ...  阅读全文
posted @ 2009-06-30 21:07 pterosaur 阅读(104) | 评论 (0)编辑 收藏

2009年6月20日

 

1. [笑话]所有进制都是10进制

人有十个手指头,这就奠定了人们常用的技术为10进制系统,数数就是这样:

1,2,3,4,5,6,7,8,9,10,11,12……

要是人一只手只有3个指头,数数就成了这样:

1,2,3,4,5,10,11,12,13,14……

其实还是10进制。

这副漫画描绘的很清楚:

 

 

2. 生活中的进制系统

可是生活中还有好多不一样的进制:

1km = 1000m, 1min = 60sec, 1day = 24hour, 1yard = 3ft, 1ft = 12inch

…………………………………………………………

计算机给我们带来了2进制,仅仅用01表示了所有的数,计算机这样数数:

1,10,11,100,101,110,111……

因此可以想想计算机只有两根手指头。

3.不安分的数学家

最不安分的是数学家,总结归纳了各种计数系统的规律,归纳出了一个通用的表达式:

(bnbn-1bn-2…b3b2b1b0.b-1b-2b-3…)N = k=-…nbkNp  (N为计数的进制,称之为“基”)

N为正整数的时候,就被称为标准N进制系统,为了保证数值的唯一表示N进制系统每一位的数值都不能超过N

 

因此就有无数种进制系统产生了。

最著名的要数3进制了。

以前看过一篇文章,说是计数进制使用基为e的进制得到的效率最高(如果存在的话),无奈e为无理数(e2.718281828……),取较为接近的整数有出现了两种系统:2进制系统和3进制系统。现在2进制系统在计算机系统种占领了主导地位,但是3进制计算机也曾经被制造过。莫斯科国立大学就生产过Сетунь 70 三进制计算机,有兴趣的参看这里.


 

Сетунь 70 结构图,懂俄文的朋友帮忙翻译下了

如果单单如此还好,不安分的数学家Vittorio Grunwald1885年首次把N变成了负数[Giornal di Matematiche di Battaglini 23(1885), 203~221, 367],他还说明了在这样的系统中如何执行四则运算,甚至讨论了如何求根。

一个简单的例子:

(1234567890)10 = (2846648290)-10

有兴趣的读者可以自行转换。

负进制系统在上世纪30年代以后有了较快的发展,上世纪50年代后期在波兰研制了叫做SKRZAT 1 BINEG 的实验性计算机,他们都采用了-2作为算术运算的进制系统。

如果说负进制系统还不能令人惊奇的话,在进制系统总引入复数则又达到了一个新高度。

例如2i进制系统可以产生出一个称为“虚4”的计数系统,它有异常的特性:每一个复数都可以不带符号地用数字0,1,2,3来表示,例如:

(12231)2i = (9-10i)10

在所有进制系统中,最美妙的应该是平衡三进制。

它是三进制的一种变形,用-1,0,1来表示各个位的权值,(据说Сетунь 70用的就是平衡三进制)它有许多有趣的性质:

a)       通过交换1-1,就可以得到一个数的相反数

b)       一个数的正负号由他的最高位的非零的数给出

c)       四舍五入运算被简化成了截断运算

另外有个数学难题”Bachet重量问题就可以通过平衡三进制来解决:

题目如下:现有一个天平,要称出1-N内所有整数重量的东西,最少需要几个砝码,每个砝码的重量是多少?

进制系统最登峰造极的高度是引入了无理进制,具体详情情参考W.Parry的论文[Acta Math. Acad. Sci. Hung. 11 (1960), 401~416]

另外除了单一进制系统外还可以将计数方法推广为混合进制系统。

最重要的混合进制系统就是阶乘数系,另外我们每天都要面对的时间也是混合进制系统。
posted @ 2009-06-20 21:03 pterosaur 阅读(232) | 评论 (0)编辑 收藏

2009年6月19日

[转自http://yueweitang.org/blog/posts/inverse-square-root-algorithm-analysis.html]

下面这个求1/\sqrt{x}的函数号称比直接调用sqrt库函数快4倍,来自游戏Quake III的源代码。

float InvSqrt(float x){
    
float xhalf = 0.5f * x;
    
int i = *(int*)&x;
    i 
= 0x5f3759df - (i >> 1);
    x 
= *(float*)&i;
    x 
= x * (1.5f - xhalf * x * x);
    
return x;
}


我们这里分析一下它的原理(指程序的正确性,而不是解释为何快)。

分析程序之前,我们必须解释一下float数据在计算机里的表示方式。一般而言,一个float数据x共32个bit,和int数据一样。其中前23位为有效数字M_x,后面接着一个8位数据E_x表示指数,最后一位表示符号,由于这里被开方的数总是大于0,所以我们暂不考虑最后一个符号位。此时

x=1.M_x 2^{E_x-127}

如果我们把计算机内的浮点数x看做一个整数I_x,那么

I_x = 2^{23}E_x+M_x

现在开始逐步分析函数。这个函数的主体有四个语句,分别的功能是:

int i = *(int*)&x; 这条语句把x转成i=I_x

i = 0×5f3759df - (i>>1); 这条语句从I_x计算I_{1/\sqrt{x}}

y = *(float*)&i; 这条语句将I_{1/\sqrt{x}}转换为1/\sqrt{x}

y = y*(1.5f - xhalf*y*y); 这时候的y是近似解;此步就是经典的牛顿迭代法。迭代次数越多越准确。

关键是第二步 i = 0x5f3759df - (i>>1); 这条语句从I_x计算I_{1/\sqrt{x}},原理:

y=1/\sqrt{x},用x=(1+m_x)2^{e_x}y=(1+m_y)2^{e_y}带入之后两边取对数,再利用近似表示\log_2(1+z)\sim z+\delta,算一算就得到

I_y = \frac{2}{3}(127-\delta)2^{23}-I_x/2

若取\delta=0.0450465679168701171875\frac{2}{3}(127-\delta)2^{23}就是程序里所用的常量0x5f3759df。至于为何选择这个\delta,则应该是曲线拟合实验的结果。

2003年Chris Lomont还写了一篇文章对这些代码进行了分析,有兴趣的读者可以下载阅读。

posted @ 2009-06-19 17:16 pterosaur 阅读(334) | 评论 (0)编辑 收藏

2009年6月6日

  明天开始今年的第三次北京之行
祝自己一帆风顺..............

1#include <stdio.h>
2int main(){
3    printf("一帆风顺!\n");
4}
posted @ 2009-06-06 20:48 pterosaur 阅读(86) | 评论 (0)编辑 收藏

2009年6月1日

用Python的Lambda运算定义的归并排序算法:
记录如下:
 1def qsort():
 2    c = lambda f, v1, v2 : \
 3        ([] if len(v2) == 0 else v2[0:1+ f(f, v1, v2[1:len(v2)])) if len(v1)==0 \
 4        else v1[0:1]+f(f,v1[1:len(v1)],v2) if len(v2) == 0 \
 5        else v1[0:1]+f(f,v1[1:len(v1)],v2) if v1[0]<v2[0] \
 6        else v2[0:1]+f(f,v1,v2[1:len(v2)]);
 7    q = lambda f, c, arr :\
 8        arr if len(arr) < 2 else \
 9        c(c, f(f, c, arr[0:int(len(arr)/2)]), f(f, c, arr[int(len(arr)/2):len(arr)]));
10    return lambda arr : q(q,c,arr);
11

效率很低,
如有更好的算法,请高手赐教
posted @ 2009-06-01 15:22 pterosaur 阅读(402) | 评论 (0)编辑 收藏
 

祝大家儿童节快乐!


 

posted @ 2009-06-01 11:38 pterosaur 阅读(143) | 评论 (0)编辑 收藏

2009年5月31日

题记:本文为第一篇技术贴
题目:给定一个输入的正整数X,求出X的所有可以被表示为 n(n>=2) 个连续正整数之和的形式:
如:15=15=7+8=4+5+6=1+2+3+4+5
(该题目可以说是骨灰级的题目了,我做了简单的改变,便于分析)
程序的实现(改方法是我能想到的最简单的一种了,如有更快的,请各位赐教)

程序代码:
int main(){
    
int exist = 0;
    
int x = 0;
    printf(
"Please input x:");
    scanf(
"%d"&x);
    
for(int n = 1; n * n < x * 2++ n){
        
int a = (2 * x / n - n + 1/ 2;
        
if( n * a + n * (n - 1/ 2 == x){
            
for(int i = 0; i < n; ++i)
                printf(
"%d ", a + i);
            printf(
"\n");
            have 
= 1;
        }

    }

    
if(!exist)
        printf(
"none\n");
}


可是题目并没有在此结束,
如果计算n的所有表示方式的种类数(记为k(n)),有如下序列(n=1..20):
1, 1, 2, 1, 2, 2, 2, 1, 3, 2, 2, 2, 2, 2, 4, 1, 2, 3, 2, 2
通过搜索,发现这个序列还有其他的含义:
1. Number of odd divisors of n;
2. Number of ways to write n as difference of two triangular numbers;
3. Number of ways to arrange n identical objects in a trapezoid;
4. Number of sums of sequences of consecutive positive integers including sequences of length 1;
5. Number of factors in the factorization of the Chebyshev polynomial of thee first kind T_n(x);
6. Number of ways to present n as sum of consecutive integers;
7. Number of factors in the factorization of the polynomial x^n+1 over the integers.
其中4就是程序所描述的方式。其描述很特别,尤其是第一个。很惊异其中的关系。
搞了很久也不知道其中的缘由,请各位赐教。
posted @ 2009-05-31 19:55 pterosaur 阅读(280) | 评论 (0)编辑 收藏

2009年5月30日

博客第一帖。

对社区的办事效率表示赞赏
posted @ 2009-05-30 16:08 pterosaur 阅读(67) | 评论 (0)编辑 收藏
CALENDER
<2019年6月>
2627282930311
2345678
9101112131415
16171819202122
23242526272829
30123456

常用链接

留言簿

随笔档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜


Powered By: 博客园
模板提供沪江博客