liangbch
发表于 2017-1-14 12:17:02
64比特的数除以\(10^9\)的商最多35比特
若硬件不支持64位数,只能做两个32位数的乘积且乘积也最多保留最低32位,那么就只能表示为\(2^{16}\)进制数再做除法了,具体做法
1.将被乘数看成4位(\(2^{16}\)进制)数,并在高位补零,变成5位数
2.将乘数看成2位(\(2^{16}\)进制)数,这样就将原问题转化为一个5位数除以2位数的问题。
3.在这里,5位数除以2位数的商为3位数,故需要做3次“3位数除以2位数”的运算。下面我们重点分析一下这个“3位数除以2位数”的子运算
3.1我们能够证明,这个3位数(48比特)最高2个比特为总是0。因为在运算过程中,余数总是小于除数,故被除数总是小于\({10}^9*2^{16}<2^{46}\)
3.2 \( a/{10^9}\)= \((a * 2^{45} / 10^9) / 2^{45}\)= \( (a * 35184.372088832)/2^{45}\)
3.3 将48位被除数记为a,除数\({10^9}\)记为d,被除数最高18位记为a0,因为最高2位为0,故a0不超过16比特,做下列运算
1. a0=a>>30, 即取a的最高18位。
2. q=a0*35184
3. q=(q>>15)
4. a -= d *q
5. 若a>d, 则q++, a-=d
6. 若a>d, 则q++, a-=d
注: 步骤1到步骤3,相当于 \(q = (a/2^{30})*35184/2^{15}= a * 35184/2^{45} \)
happysxyf
发表于 2017-1-14 12:31:07
uint64_t a, q;
q= a-((a>>30)<<30)
BBP算法是计算16进制的派,我觉得可以先弄成16进制的,在转化为10进制。
liangbch
发表于 2017-1-14 13:37:31
说明:
1。若被除数的范围更小,小于\(2^{32}*{10}^9\), 则只需2次除法。
2. 由于第一次除法中,被除数远小于\2^46\), 故可将试商步骤改为如下序列,减少一次调整商步骤。
1. a0=a>>16, 即取a的中16位。
2. q=a0*35184
3. q=(q>>29)
4. a -= d *q
5. 若a>d, 则q++, a-=d
gxqcn
发表于 2017-1-14 14:23:05
需要注意对方需求的特别之处,仅需返回一个布尔值即可。
happysxyf
发表于 2017-1-14 15:03:43
本帖最后由 happysxyf 于 2017-1-14 15:45 编辑
基本实现,只要允许使用while循环和数组,下面代码就成立。不知题目中的纳秒是什么数量级,是C#中的纳秒,还是10的-9次方秒。我只能做到0.0000001秒出结果。并且全程没用任何乘除。
/*COPYRIGHT@2016~2018 BY HAPPY*/
#include <stdio.h>
typedef unsigned long long uint64_t;
static const int mang={1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 73741824, 147483648, 294967296, 589934592, 179869184, 359738368, 719476736, 438953472, 877906944, 755813888, 511627776, 23255552, 46511104, 93022208, 186044416, 372088832, 744177664, 488355328, 976710656, 953421312, 906842624, 813685248, 627370496, 254740992, 509481984, 18963968, 37927936, 75855872, 151711744, 303423488, 606846976, 213693952, 427387904, 854775808};
//uint64_t取余函数
int Uint64ModBillion(uint64_t a)
{
int S=0, *p=(int*)mang;
while(a){
if(a-((a>>1)<<1)){
S+=*p, S=(S>=1000000000)?S-=1000000000:S;
}
a>>=1, p++;
}
return S;
}
//主函数入口
int main()
{
uint64_t a=8446744073709551616;
printf("%d\n", Uint64ModBillion(a));
return 0;
}
下面是返回bool类型的函数
/*COPYRIGHT@2016~2018 BY HAPPY*/
#include <stdio.h>
#include <stdbool.h>
typedef unsigned long long uint64_t;
typedef unsigned long uint32_t;
static const uint32_t mang={1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 73741824, 147483648, 294967296, 589934592, 179869184, 359738368, 719476736, 438953472, 877906944, 755813888, 511627776, 23255552, 46511104, 93022208, 186044416, 372088832, 744177664, 488355328, 976710656, 953421312, 906842624, 813685248, 627370496, 254740992, 509481984, 18963968, 37927936, 75855872, 151711744, 303423488, 606846976, 213693952, 427387904, 854775808};
//uint64_t取余函数
bool Uint64ModBillion(uint64_t a)
{
uint32_t S=0, *p=(uint32_t*)mang;
while(a){
if(a-((a>>1)<<1)){
S+=*p, S=(S>=1000000000)?S-=1000000000:S;
};
a>>=1, p++;
}
return (S<500000000)?true:false;
}
//主函数入口
void main()
{
uint64_t a=8073709551616;
Uint64ModBillion(a)?fputs("TRUE\n", stdout):fputs("FALSE\n", stdout);
}
liangbch
发表于 2017-1-15 10:42:06
楼上的代码可以进一步优化,实际上a最低的29bit是无需查表计算的,跳过最低的29比特,最大循环次数可从64减少到36.
static const uint32_t mang[]=
{
536870912, 73741824, 147483648,
294967296, 589934592, 179869184, 359738368, 719476736, 438953472, 877906944, 755813888,
511627776, 23255552, 46511104, 93022208, 186044416, 372088832, 744177664, 488355328,
976710656, 953421312, 906842624, 813685248, 627370496, 254740992, 509481984, 18963968,
37927936, 75855872, 151711744, 303423488, 606846976, 213693952, 427387904, 854775808
};
//uint64_t取余函数
bool Uint64ModBillion2(uint64_t a)
{
uint32_t S;
uint32_t *p=(uint32_t*)mang;
S= a & ( (1<<29)-1);
a>>=29;
while (a)
{
if (a & 1)
{
S+=*p, S=(S>=1000000000)?S-=1000000000:S;
};
a>>=1, p++;
}
return (S<500000000)?true:false;
}
liangbch
发表于 2017-1-15 10:43:50
还有, 我把 ”if(a-((a>>1)<<1))“ 改成了 “if (a & 1)”
mathe
发表于 2017-1-15 11:12:23
应该考虑一下将除以常数转化为乘以常数的算法,而且最终我们只需要取其中一个比特的信息
liangbch
发表于 2017-1-15 11:16:01
mathe 发表于 2017-1-15 11:12
应该考虑一下将除以常数转化为乘以常数的算法,而且最终我们只需要取其中一个比特的信息
11楼就是这个方法呀,我想不出更快的算法。
只是呼吸
发表于 2017-1-15 12:39:48
基本实现,只要允许使用while循环和数组,下面代码就成立。不知题目中的纳秒是什么数量级,是C#中的纳秒,还是10的-9次方秒。我只能做到0.0000001秒出结果。并且全程没用任何乘除。
happysxyf写的这个程序,我试了几个数,结果是对的。你们都厉害啊,乘法、除法都不用,就把除法做出来了。看来除法指令是给我们初学者安排的。
我猜测 liangbch 对这类问题有研究,会更好些。