- c - 在位数组中找到第一个零
- linux - Unix 显示有关匹配两种模式之一的文件的信息
- 正则表达式替换多个文件
- linux - 隐藏来自 xtrace 的命令
我正在解决 this problem ,其中他们要求第一个 1000 位斐波那契数的索引,我的第一个想法类似于:
BigInteger x = 1;
BigInteger y = 1;
BigInteger tmp = 0;
int currentIndex = 2;
while (x.NoOfDigits < 1000)
{
tmp = x + y;
y = x;
x = tmp;
currentIndex++;
}
return currentIndex;
但是,据我所知,没有计算 BigInteger 位数的方法。这是真的?绕过它的一种方法是使用 BigInteger 的 .ToString().Length 方法,但有人告诉我字符串处理速度很慢。
BigInteger 也有一个 .ToByteArray(),我想将 BigInteger 转换为字节数组并检查该数组的长度 - 但我认为这不能唯一地确定 BigInteger 中的位数。
为了它的值(value),我实现了另一种解决它的方法,即手动将斐波那契数存储在数组中,并在数组已满时立即停止,我将其与基于 .ToString 的方法进行了比较,后者慢了大约2.5倍,但是第一种方法用了0.1秒,也显得很长。
编辑:我已经测试了下面答案中的两个建议(一个使用 BigInteger.Log,另一个使用 MaxLimitMethod)。我得到以下运行时间:
程序
using System;
using System.Collections.Generic;
using System.Numerics;
using System.Diagnostics;
class Program
{
static void Main(string[] args)
{
Stopwatch clock = new Stopwatch();
clock.Start();
int index1 = Algorithms.IndexOfNDigits(1000);
clock.Stop();
var elapsedTime1 = clock.Elapsed;
Console.WriteLine(index1);
Console.WriteLine("Original method: {0}",elapsedTime1);
Console.ReadKey();
clock.Reset();
clock.Start();
int index2 = Algorithms.StringMethod(1000);
clock.Stop();
var elapsedTime2 = clock.Elapsed;
Console.WriteLine(index2);
Console.WriteLine("StringMethod: {0}", elapsedTime2);
Console.ReadKey();
clock.Reset();
clock.Start();
int index3 = Algorithms.BigIntegerLogMethod(1000);
clock.Stop();
var elapsedTime3 = clock.Elapsed;
Console.WriteLine(index3);
Console.WriteLine("BigIntegerLogMethod: {0}", elapsedTime3);
Console.ReadKey();
clock.Reset();
clock.Start();
int index4 = Algorithms.MaxLimitMethod(1000);
clock.Stop();
var elapsedTime4 = clock.Elapsed;
Console.WriteLine(index4);
Console.WriteLine("MaxLimitMethod: {0}", elapsedTime4);
Console.ReadKey();
}
}
static class Algorithms
{
//Find the index of the first Fibonacci number of n digits
public static int IndexOfNDigits(int n)
{
if (n == 1) return 1;
int[] firstNumber = new int[n];
int[] secondNumber = new int[n];
firstNumber[0] = 1;
secondNumber[0] = 1;
int currentIndex = 2;
while (firstNumber[n-1] == 0)
{
int carry = 0, singleSum = 0;
int[] tmp = new int[n]; //Placeholder for the sum
for (int i = 0; i<n; i++)
{
singleSum = firstNumber[i] + secondNumber[i];
if (singleSum >= 10) carry = 1;
else carry = 0;
tmp[i] += singleSum % 10;
if (tmp[i] >= 10)
{
tmp[i] = 0;
carry = 1;
}
int countCarries = 0;
while (carry == 1)
{
countCarries++;
if (tmp[i + countCarries] == 9)
{
tmp[i + countCarries] = 0;
tmp[i + countCarries + 1] += 1;
carry = 1;
}
else
{
tmp[i + countCarries] += 1;
carry = 0;
}
}
}
for (int i = 0; i < n; i++ )
{
secondNumber[i] = firstNumber[i];
firstNumber[i] = tmp[i];
}
currentIndex++;
}
return currentIndex;
}
public static int StringMethod(int n)
{
BigInteger x = 1;
BigInteger y = 1;
BigInteger tmp = 0;
int currentIndex = 2;
while (x.ToString().Length < n)
{
tmp = x + y;
y = x;
x = tmp;
currentIndex++;
}
return currentIndex;
}
public static int BigIntegerLogMethod(int n)
{
BigInteger x = 1;
BigInteger y = 1;
BigInteger tmp = 0;
int currentIndex = 2;
while (Math.Floor(BigInteger.Log10(x) + 1) < n)
{
tmp = x + y;
y = x;
x = tmp;
currentIndex++;
}
return currentIndex;
}
public static int MaxLimitMethod(int n)
{
BigInteger maxLimit = BigInteger.Pow(10, n - 1);
BigInteger x = 1;
BigInteger y = 1;
BigInteger tmp = 0;
int currentIndex = 2;
while (x.CompareTo(maxLimit) < 0)
{
tmp = x + y;
y = x;
x = tmp;
currentIndex++;
}
return currentIndex;
}
}
最佳答案
前提是x > 0
int digits = (int)Math.Floor(BigInteger.Log10(x) + 1);
会得到位数。
出于好奇,我测试了
int digits = x.ToString().Length;
方法。对于 100 000 000 次迭代,它比 Log10 解决方案慢 3 倍。
关于c# - 我可以在 C# 中找到 BigInteger 的位数吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34052376/
我正在尝试计算一个大数,这需要 BigInteger.Pow(),但我需要指数也是 BigInteger 而不是 整数。 即 BigInteger.Pow(BigInteger) 我怎样才能做到这一点
在 Java 中,大多数基本类型都是有符号的(一位用于表示 +/-),因此当我超出类型的限制时,我会得到意想不到的结果,比如负数。 有没有比使用 BigInteger 更好的解决方案,因为 BigIn
如何选择随机元素 α ∈ Z*p? P 是一个随机的 1024 位素数 BigInteger。 这是我找到 BigInteger p 的方法: Random rand = new Random(new
我正在尝试使用 BigInteger 类在 Java 中实现 Fermat、Miller-Rabin 或 AKS 算法。 我想我有Fermat test已实现,但 BigInteger 类不允许将 B
我知道 BigInteger 有一个构造函数,您可以在其中通过传递新 BigInteger 的最大 bitLength 和一个随机参数来生成随机 BigInteger: BigInteger(int
我正在考虑为自己存储公钥的想法。为此,我需要将 BigInteger 转换为某种变量,然后从该值重新创建 BigInteger。 我在 Stackoverflow 中进行了搜索,找到了执行此操作的最佳
目前我正在使用 Long 整数类型。我使用以下方法从/到二进制/数字进行转换: Convert.ToInt64(BinaryString, 2); //Convert binary string of
我有以下代码: public static BigInteger[] Cubes (int m){ Set result = new HashSet(); for (int i = 1
因此,在我的计算机科学课上,我们一直在学习如何使用 Java 编码,并且我遇到了编码本身的第一个局限性。问题是 long 只允许您存储最多 64 位或接近该位的数字。所以我们已经开始用 16 位数字进
你好我想计算 2^(256bit number) 在 java 中,但 biginteger 的 pow 函数只能处理 int。 如何计算更大的数字? 有图书馆吗? 我想计算来自的所有数字 2^0 2
我正在尝试构建一个 BigInteger 数组,但似乎该数组需要由整数本身索引(如果是这样,那对我来说似乎非常愚蠢,但我希望我只是误解了一些东西) .我正在尝试的基本上是以下内容: BigIntege
我在 .Net 项目中使用 BigInteger ( link ) 的单声道实现在 Java 中我使用 java.math.BigInteger。 相同的代码在 Java 中产生不同的结果。 .Net
我正在构建 DSA 算法。但是在将 BigInteger 数字与其他 BigInteger 数字进行排名时遇到了问题。这是我要使用的公式: v = ((g^u1 * y^u2) mod p) mod
我正在尝试用Java实现Schnorr签名算法。我遇到了计算大指数幂(例如 MD5 哈希值)的问题。 有什么方法可以让BigInteger获得BigInteger的权力吗? 我需要计算 (a^x*b^
我正在编写斐波那契程序。 public class ImperativeFibonacci implements Fibonacci { public BigInteger fibonacci(i
我原以为 BigInteger 类中的两个构造函数 BigInteger(String) 和 BigInteger(byte[]) 的行为相似,但事实并非如此。 为什么两个 BigInteger 不相
在 Java 中,要将 String 转换为 BigInteger,您可以使用构造函数 new BigInteger(String),但要将 int/long 转换为工厂函数,您可以使用 BigInt
我正在做一些大整数计算,我需要对一个 BigInteger 求另一个 BigInteger 的幂。 .pow() 方法执行我想要的操作,但将 int 值作为参数。 .modPow 方法采用 BigIn
Java 7 方法的复杂性是什么pow和 isProbablePrime在BigInteger类(class)? 我知道 Rabin 测试的简单实现具有 O(k(log(n))^3) 复杂度,可以通过
.NET 4.0 为任意大的整数提供了 System.Numerics.BigInteger 类型。我需要计算 BigInteger 的平方根(或合理的近似值——例如整数平方根)。这样我就不必重新实现
我是一名优秀的程序员,十分优秀!