The problem is to derive a formula for determining number of digits a given decimal number could have in a given base.
问题是推导出一个公式来确定一个给定的小数在一个给定的基数上可能有多少位。
For example: The decimal number 100006 can be represented by 17,11,9,8,7,6,8 digits in bases 2,3,4,5,6,7,8 respectively.
例如:十进制数字100006可以用17、11、9、8、7、6、8位数字来表示，分别在2、3、4、5、6、7、8个数字中。
Well the formula I derived so far is like this : (log10(num) /log10(base)) + 1.
到目前为止我推导的公式是这样的:(log10(num) /log10(base)) + 1。
in C/C++ I used this formula to compute the above given results.
在C/ c++中，我使用这个公式来计算上述给定的结果。
long long int size = ((double)log10(num) / (double)log10(base)) + 1.0;
长长整数大小=(双)log10(num) /(双)log10(base) + 1.0;
But sadly the formula is not giving correct answer is some cases,like these :
但遗憾的是，这个公式并没有给出正确答案，有些情况是这样的:
Number 8 in base 2 : 1,0,0,0
Number of digits: 4
Formula returned: 3
Number 64 in base 2 : 1,0,0,0,0,0,0
Number of digits: 7
Formula returned: 6
Number 64 in base 4 : 1,0,0,0
Number of digits: 4
Formula returned: 3
Number 125 in base 5 : 1,0,0,0
Number of digits: 4
Formula returned: 3
Number 128 in base 2 : 1,0,0,0,0,0,0,0
Number of digits: 8
Formula returned: 7
Number 216 in base 6 : 1,0,0,0
Number of digits: 4
Formula returned: 3
Number 243 in base 3 : 1,0,0,0,0,0
Number of digits: 6
Formula returned: 5
Number 343 in base 7 : 1,0,0,0
Number of digits: 4
Formula returned: 3
So the error is by 1 digit.I just want somebody to help me to correct the formula so that it work for every possible cases.
误差是1位。我只是希望有人能帮我修正一下公式这样它就能适用于所有可能的情况。
Edit : As per the input specification I have to deal with cases like 10000000000, i.e 10^10,I don't think log10() in either C/C++ can handle such cases ? So any other procedure/formula for this problem will be highly appreciated.
编辑:根据输入规范，我需要处理10000000000,I。e 10 ^,我不认为log10()C / c++可以处理这种情况?因此，对于这个问题的任何其他程序或公式，我们将非常感激。
13 个解决方案
#1
8
There are fast floating operations in your compiler settings. You need precise floation operations. The thing is that log10(8)/log10(2) is always 3 in math. But may be your result is 2.99999, for expample. It is bad. You must add small additive, but not 0.5. It should be about .00001 or something like that.
在编译器设置中有快速浮动操作。你需要精确的漂浮操作。问题是log10(8)/log10(2)在数学上总是3。但可能是你的结果是2.99999，为了充分说明。它是坏的。必须添加小的添加剂，但不能添加0.5。应该是0。00001之类的。
Almost true formula:
几乎正确的公式:
int size = static_cast<int>((log10((double)num) / log10((double)base)) + 1.00000001);
Really true solution
真的解决方案
You should check the result of your formula. Compexity is O(log log n) or O(log result)!
你应该检查一下公式的结果。Compexity是O(log log n)或O(log result)!
int fast_power(int base, int s)
{
int res = 1;
while (s) {
if (s%2) {
res*=base;
s--;
} else {
s/=2;
base*=base;
}
}
return res;
}
int digits_size(int n, int base)
{
int s = int(log10(1.0*n)/log10(1.0*base)) + 1;
return fast_power(base, s) > n ? s : s+1;
}
This check is better than Brute-force test with base multiplications.
这个检验比用基本乘法的蛮力检验要好。
#2
7
Either of the following will work:
以下任何一种都可以:
>>> from math import *
>>> def digits(n, b=10):
... return int(1 + floor(log(n, b))) if n else 1
...
>>> def digits(n, b=10):
... return int(ceil(log(n + 1, b))) if n else 1
...
The first version is explained at mathpath.org. In the second version the + 1 is necessary to yield the correct answer for any number n that is the smallest number with d digits in base b. That is, those numbers which are written 10...0 in base b. Observe that input 0 must be treated as a special case.
第一个版本在mathpath.org上解释。在第二种版本中，对于以b为基数的d位数最小的任何数字n， + 1都必须给出正确的答案。以b为底的0。注意输入0必须被当作一个特殊情况来处理。
Decimal examples:
小数的例子:
>>> digits(1)
1
>>> digits(9)
1
>>> digits(10)
2
>>> digits(99)
2
>>> digits(100)
3
Binary:
二:
>>> digits(1, 2)
1
>>> digits(2, 2)
2
>>> digits(3, 2)
2
>>> digits(4, 2)
3
>>> digits(1027, 2)
11
Edit: The OP states that the log solution may not work for large inputs. I don't know about that, but if so, the following code should not break down, because it uses integer arithmetic only (this time in C):
编辑:OP声明日志解决方案可能不适用于大型输入。我不知道，如果是的话，下面的代码不应该崩溃，因为它只使用整数算法(这次是C):
unsigned int
digits(unsigned long long n, unsigned long long b)
{
unsigned int d = 0;
while (d++, n /= b);
return d;
}
This code will probably be less efficient. And yes, it was written for maximum obscurity points. It simply uses the observation that every number has at least one digit, and that every divison by b which does not yield 0 implies the existence of an additional digit. A more readable version is the following:
这段代码的效率可能会降低。是的，它是为最大模糊点而写的。它简单地使用了每一个数字至少有一个数字的观察结果，并且每一个不产生0的因子b都意味着一个额外的数字的存在。一个可读性更好的版本是:
unsigned int
digits(unsigned long long n, unsigned long long b)
{
unsigned int d = 1;
while (n /= b) {
d++;
}
return d;
}
#4
3
Since your formula is correct (I just tried it), I would think that it's a rounding error in your division, causing the number to be just slightly less than the integer value it should be. So when you truncate to an integer, you lose 1. Try adding an additional 0.5 to your final value (so that truncating is actually a round operation).
由于你的公式是正确的(我刚刚试过)，我认为这是除法中的舍入误差，导致这个数比它应该的整数值稍微小一点。当你截断到一个整数时，你会损失1。尝试在最终值上再增加一个0.5(这样截断实际上是一个圆形操作)。
#5
2
What you want is ceiling ( = smallest integer not greater than) logb (n+1), rather than what you're calculating right now, floor(1+logb(n)).
你想要的是上限(=最小整数不大于)logb(n +1)，而不是你现在计算的楼层(1+logb(n)))。
You might try:
你可以试一试:
int digits = (int) ceil( log((double)(n+1)) / log((double)base) );
#6
1
As others have pointed out, you have rounding error, but the proposed solutions simply move the danger zone or make it smaller, they don't eliminate it. If your numbers are integers then you can verify -- using integer arithmetic -- that one power of the base is less than or equal to your number, and the next is above it (the first power is the number of digits). But if you use floating point arithmetic anywhere in the chain then you will be vulnerable to error (unless your base is a power of two, and maybe even then).
正如其他人指出的那样，你有四舍五入的错误，但建议的解决方案只是简单地移动危险区域或使其变小，他们不会消除它。如果你的数字是整数，那么你可以用整数算术来验证底的一次方小于或等于你的数字，下一次方在它上面(第一次方是数字的个数)。但是如果你在链中的任何地方使用浮点算法，那么你将很容易出错(除非你的底是2的幂，甚至可能是2的幂)。
EDIT:
Here is crude but effective solution in integer arithmetic. If your integer classes can hold numbers as big as base*number, this will give the correct answer.
编辑:这是一个简单但有效的整数算法解决方案。如果您的整数类可以容纳与基数*number一样大的数字，这将给出正确的答案。
size = 0, k = 1;
while(k<=num)
{
k *= base;
size += 1;
}
#7
1
Using your formula,
使用你的公式,
log(8)/log(2) + 1 = 4
the problem is in the precision of the logarithm calculation. Using
问题在于对数计算的精度。使用
ceil(log(n+1)/log(b))
ought to resolve that problem. This isn't quite the same as
应该解决这个问题。这和
ceil(log(n)/log(b))
because this gives the answer 3 for n=8 b=2, nor is it the same as
因为这给出了n=8 b=2的答案，也不等于。
log(n+1)/log(b) + 1
because this gives the answer 4 for n=7 b=2 (when calculated to full precision).
因为这给出了n= 7b =2的答案4(当计算到完全精度时)。
I actually get some curious resulting implementing and compiling the first form with g++:
实际上，我得到了一些奇怪的结果，使用g++实现并编译第一个表单:
double n = double(atoi(argv[1]));
double b = double(atoi(argv[2]));
int i = int(std::log(n)/std::log(b) + 1.0);
fails (IE gives the answer 3), while,
失败(即给出答案3)，
double v = std::log(n)/std::log(b) + 1.0;
int i = int(v);
succeeds (gives the answer 4). Looking at it some more I think a third form
成功(给出答案4).再看看它，我想是第三种形式
ceil(log(n+0.5)/log(b))
would be more stable, because it avoids the "critical" case when n (or n+1 for the second form) is an integer power of b (for integer values of n).
更稳定，因为它避免了当n(或n+1为第二种形式)是b的整数次幂(n为整数)时的“临界”情况。
#8
0
It may be beneficial to wrap a rounding function (e.g. + 0.5) into your code somewhere: it's quite likely that the division is producing (e.g.) 2.99989787, to which 1.0 is added, giving 3.99989787 and when that's converted to an int, it gives 3.
将一个舍入函数(例如+ 0.5)封装到代码中可能是有益的:很有可能这个部门正在生成(例如)2.99989787，其中增加了1.0，得到3.99989787，当它转换为int时，得到3。
#9
0
Looks like the formula is right to me:
看起来这个公式对我来说是对的:
Number 8 in base 2 : 1,0,0,0
Number of digits: 4
Formula returned: 3
log10(8) = 0.903089
log10(2) = 0.301029
Division => 3
+1 => 4
So it's definitely just a rounding error.
这绝对是舍入误差。
#10
0
Floating point rounding issues.
浮点舍入的问题。
log10(216) / log10(6) = 2.9999999999999996
But you cannot add 0.5 as suggested, because it would not work for the following
但是您不能按照建议添加0.5，因为它对下面的操作不起作用
log10(1295) = log10(6) = 3.9995691928566091 // 5, 5, 5, 5
log10(1296) = log10(6) = 4.0 // 1, 0, 0, 0, 0
Maybe using the log(value, base) function would avoid these rounding errors.
也许使用log(value, base)函数可以避免这些舍入错误。
#11
0
I think that the only way to get the rounding error eliminated without producing other errors is to use or implement integer logarithms.
我认为消除舍入误差而不产生其他误差的唯一方法是使用或实现整数对数。
#12
0
Here is a solution in bash:
在bash中有一个解决方案:
% digits() { echo $1 $2 opq | dc | sed 's/ .//g;s/.//' | wc -c; }
% digits 10000000000 42
7
#13
0
static int numInBase(int num, int theBase)
{
if(num == 0) return 0;
if (num == theBase) return 1;
return 1 + numInBase(num/theBase,theBase);
}
#1
8
There are fast floating operations in your compiler settings. You need precise floation operations. The thing is that log10(8)/log10(2) is always 3 in math. But may be your result is 2.99999, for expample. It is bad. You must add small additive, but not 0.5. It should be about .00001 or something like that.
在编译器设置中有快速浮动操作。你需要精确的漂浮操作。问题是log10(8)/log10(2)在数学上总是3。但可能是你的结果是2.99999，为了充分说明。它是坏的。必须添加小的添加剂，但不能添加0.5。应该是0。00001之类的。
Almost true formula:
几乎正确的公式:
int size = static_cast<int>((log10((double)num) / log10((double)base)) + 1.00000001);
Really true solution
真的解决方案
You should check the result of your formula. Compexity is O(log log n) or O(log result)!
你应该检查一下公式的结果。Compexity是O(log log n)或O(log result)!
int fast_power(int base, int s)
{
int res = 1;
while (s) {
if (s%2) {
res*=base;
s--;
} else {
s/=2;
base*=base;
}
}
return res;
}
int digits_size(int n, int base)
{
int s = int(log10(1.0*n)/log10(1.0*base)) + 1;
return fast_power(base, s) > n ? s : s+1;
}
This check is better than Brute-force test with base multiplications.
这个检验比用基本乘法的蛮力检验要好。
#2
7
Either of the following will work:
以下任何一种都可以:
>>> from math import *
>>> def digits(n, b=10):
... return int(1 + floor(log(n, b))) if n else 1
...
>>> def digits(n, b=10):
... return int(ceil(log(n + 1, b))) if n else 1
...
The first version is explained at mathpath.org. In the second version the + 1 is necessary to yield the correct answer for any number n that is the smallest number with d digits in base b. That is, those numbers which are written 10...0 in base b. Observe that input 0 must be treated as a special case.
第一个版本在mathpath.org上解释。在第二种版本中，对于以b为基数的d位数最小的任何数字n， + 1都必须给出正确的答案。以b为底的0。注意输入0必须被当作一个特殊情况来处理。
Decimal examples:
小数的例子:
>>> digits(1)
1
>>> digits(9)
1
>>> digits(10)
2
>>> digits(99)
2
>>> digits(100)
3
Binary:
二:
>>> digits(1, 2)
1
>>> digits(2, 2)
2
>>> digits(3, 2)
2
>>> digits(4, 2)
3
>>> digits(1027, 2)
11
Edit: The OP states that the log solution may not work for large inputs. I don't know about that, but if so, the following code should not break down, because it uses integer arithmetic only (this time in C):
编辑:OP声明日志解决方案可能不适用于大型输入。我不知道，如果是的话，下面的代码不应该崩溃，因为它只使用整数算法(这次是C):
unsigned int
digits(unsigned long long n, unsigned long long b)
{
unsigned int d = 0;
while (d++, n /= b);
return d;
}
This code will probably be less efficient. And yes, it was written for maximum obscurity points. It simply uses the observation that every number has at least one digit, and that every divison by b which does not yield 0 implies the existence of an additional digit. A more readable version is the following:
这段代码的效率可能会降低。是的，它是为最大模糊点而写的。它简单地使用了每一个数字至少有一个数字的观察结果，并且每一个不产生0的因子b都意味着一个额外的数字的存在。一个可读性更好的版本是:
unsigned int
digits(unsigned long long n, unsigned long long b)
{
unsigned int d = 1;
while (n /= b) {
d++;
}
return d;
}
#3
#4
3
Since your formula is correct (I just tried it), I would think that it's a rounding error in your division, causing the number to be just slightly less than the integer value it should be. So when you truncate to an integer, you lose 1. Try adding an additional 0.5 to your final value (so that truncating is actually a round operation).
由于你的公式是正确的(我刚刚试过)，我认为这是除法中的舍入误差，导致这个数比它应该的整数值稍微小一点。当你截断到一个整数时，你会损失1。尝试在最终值上再增加一个0.5(这样截断实际上是一个圆形操作)。
#5
2
What you want is ceiling ( = smallest integer not greater than) logb (n+1), rather than what you're calculating right now, floor(1+logb(n)).
你想要的是上限(=最小整数不大于)logb(n +1)，而不是你现在计算的楼层(1+logb(n)))。
You might try:
你可以试一试:
int digits = (int) ceil( log((double)(n+1)) / log((double)base) );
#6
1
As others have pointed out, you have rounding error, but the proposed solutions simply move the danger zone or make it smaller, they don't eliminate it. If your numbers are integers then you can verify -- using integer arithmetic -- that one power of the base is less than or equal to your number, and the next is above it (the first power is the number of digits). But if you use floating point arithmetic anywhere in the chain then you will be vulnerable to error (unless your base is a power of two, and maybe even then).
正如其他人指出的那样，你有四舍五入的错误，但建议的解决方案只是简单地移动危险区域或使其变小，他们不会消除它。如果你的数字是整数，那么你可以用整数算术来验证底的一次方小于或等于你的数字，下一次方在它上面(第一次方是数字的个数)。但是如果你在链中的任何地方使用浮点算法，那么你将很容易出错(除非你的底是2的幂，甚至可能是2的幂)。
EDIT:
Here is crude but effective solution in integer arithmetic. If your integer classes can hold numbers as big as base*number, this will give the correct answer.
编辑:这是一个简单但有效的整数算法解决方案。如果您的整数类可以容纳与基数*number一样大的数字，这将给出正确的答案。
size = 0, k = 1;
while(k<=num)
{
k *= base;
size += 1;
}
#7
1
Using your formula,
使用你的公式,
log(8)/log(2) + 1 = 4
the problem is in the precision of the logarithm calculation. Using
问题在于对数计算的精度。使用
ceil(log(n+1)/log(b))
ought to resolve that problem. This isn't quite the same as
应该解决这个问题。这和
ceil(log(n)/log(b))
because this gives the answer 3 for n=8 b=2, nor is it the same as
因为这给出了n=8 b=2的答案，也不等于。
log(n+1)/log(b) + 1
because this gives the answer 4 for n=7 b=2 (when calculated to full precision).
因为这给出了n= 7b =2的答案4(当计算到完全精度时)。
I actually get some curious resulting implementing and compiling the first form with g++:
实际上，我得到了一些奇怪的结果，使用g++实现并编译第一个表单:
double n = double(atoi(argv[1]));
double b = double(atoi(argv[2]));
int i = int(std::log(n)/std::log(b) + 1.0);
fails (IE gives the answer 3), while,
失败(即给出答案3)，
double v = std::log(n)/std::log(b) + 1.0;
int i = int(v);
succeeds (gives the answer 4). Looking at it some more I think a third form
成功(给出答案4).再看看它，我想是第三种形式
ceil(log(n+0.5)/log(b))
would be more stable, because it avoids the "critical" case when n (or n+1 for the second form) is an integer power of b (for integer values of n).
更稳定，因为它避免了当n(或n+1为第二种形式)是b的整数次幂(n为整数)时的“临界”情况。
#8
0
It may be beneficial to wrap a rounding function (e.g. + 0.5) into your code somewhere: it's quite likely that the division is producing (e.g.) 2.99989787, to which 1.0 is added, giving 3.99989787 and when that's converted to an int, it gives 3.
将一个舍入函数(例如+ 0.5)封装到代码中可能是有益的:很有可能这个部门正在生成(例如)2.99989787，其中增加了1.0，得到3.99989787，当它转换为int时，得到3。
#9
0
Looks like the formula is right to me:
看起来这个公式对我来说是对的:
Number 8 in base 2 : 1,0,0,0
Number of digits: 4
Formula returned: 3
log10(8) = 0.903089
log10(2) = 0.301029
Division => 3
+1 => 4
So it's definitely just a rounding error.
这绝对是舍入误差。
#10
0
Floating point rounding issues.
浮点舍入的问题。
log10(216) / log10(6) = 2.9999999999999996
But you cannot add 0.5 as suggested, because it would not work for the following
但是您不能按照建议添加0.5，因为它对下面的操作不起作用
log10(1295) = log10(6) = 3.9995691928566091 // 5, 5, 5, 5
log10(1296) = log10(6) = 4.0 // 1, 0, 0, 0, 0
Maybe using the log(value, base) function would avoid these rounding errors.
也许使用log(value, base)函数可以避免这些舍入错误。
#11
0
I think that the only way to get the rounding error eliminated without producing other errors is to use or implement integer logarithms.
我认为消除舍入误差而不产生其他误差的唯一方法是使用或实现整数对数。
#12
0
Here is a solution in bash:
在bash中有一个解决方案:
% digits() { echo $1 $2 opq | dc | sed 's/ .//g;s/.//' | wc -c; }
% digits 10000000000 42
7
#13
0
static int numInBase(int num, int theBase)
{
if(num == 0) return 0;
if (num == theBase) return 1;
return 1 + numInBase(num/theBase,theBase);
}