So, what I basically need is to calculate value of an exponential function (2^n)*(2^(n-1)-1) using c , where n is a unsigned int type user input. Since n can be assigned any value in unsigned int range, I cannot simply calculate function value and assign it to some unsigned int variable (because resulting number will clearly be out of said range). Therefore, it seems reasonable to me to somehow get my desired function value number by number and write each number as a array element. The only struggle is to realise this method.
Any ideas (both using proposed method or any other one) would be much appreciated.
edit: Right now I have the following code:
outdated
As expected, it will only work with small values of n
Edit 2: as one of the commentators suggested, I've done some binary numbers by hand. It was pretty fruitful, but I still need sime assistance. Now i have the following code, which will correctly output binary value of said function:
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
class Exp {
private:
unsigned int n;
char* dec;
string bin;
char* hex;
public:
Exp(){
n = 0;
bin = '0';
dec = 0;
hex = 0;
};
Exp(unsigned int);
operator char* ();
};
Exp::Exp(unsigned int nn) {
n = nn;
bin=string(nn, '1');
bin =string(nn 1, '0');
}
Exp::operator char *() {
static char str[3200];
cout << "binary - " << bin << endl;
return str;
}
int main(int argc, char* argv[]) {
int n;
if (argc != 2){
cout << "Incorrect number of arguments" << endl;
exit (2);
}
if ((sscanf(argv[1], "%u", &n) != 1) or ((n < 2) or (n > 4294967295))){
cout << "incorrect exp value" << endl;
exit (-3);
}
Exp num(n);
cout << (char*) num << endl;
};
The only thing left is to convert this value to decimal and hexadecimal. I am not experienced at working with string class, so advice would be appreciated.
CodePudding user response：
You can use unsigned long or unsigned long long (or uintX_t where X is the maximum supported size on your platform) if unsigned int cannot hold your output. If that's still not enough for your use case, then either implement your own big integer class, or use an existing library (recommended if you can afford it). There are a couple of them out there. For example, GNU Multiple Precision Arithmetic Library (GMP) and bigint-library. See this list for more.
In case you decided to go on your own and implement your own class, this might give you some clues on how to start. (Note that, for efficiency matters, number theory algorithms may be applied. It is not an easy task to come with a good implementation).
template<typename T = unsigned, int Base = 10> class Bigint {
std::vector<T> digits;
bool sign; // For e.g. true for or 0, false for -
public:
Bigint() : digits(), sign(true) { }
Bigint(int x)
{
// Insert digits of x into digits vector
// Don't forget the sign
}
// Do the same with other types: short, long, unsigned, etc.
Bigint(const char *x)
{
// You need to parse x. Bad formatting is to be handled (tip: use exceptions)
}
// Provide an std::string version
Bigint(const Bigint& bi) : digits(bi.digits), sign(bi.sign) {}
Bigint& operator=(const Bigint& bi)
{
// Copy...
return *this;
}
// You also have to implement operators
Bigint& operator (const Bigint& bi)
{
// Logic...
return *this;
}
// Other operators: -, /, %, bitwise, etc.
// Tip: you can use a helper class to be used by both / and % since they share a similar logic (for avoiding redundant code).
Bigint power(const Bigint& bi) // Provide other signatures: int, string, etc.
{
// Logic...
}
};
CodePudding user response：
For 16 bit ints it's doable and produces about 40k decimal chars. For 32 bit ints, not so much as it's about 10^20 decimal chars which is beyond anything possible. Even outputting a million chars per second would take longer than the lifetime of the universe.
Here's code for 16 bit ints. Runs in about 3 seconds for n = 65535 not including output time. It has performance improvements by accumulating base 10 sums and normalizing occasionally to prevent overflow.
#include <iostream>
#include <vector>
#include <string>
#include <cstdint>
using std::cout;
using std::vector;
using std::string;
struct BigDecPower2 {
static constexpr uint32_t Normalize_Max{ 26 }; // int8:3, int16:10, int32:26
vector<uint32_t> v;
uint32_t top;
uint32_t normalize_count;
BigDecPower2(uint32_t n) : v(n), top(0), normalize_count(0) {};
void normalize()
{
normalize_count = 0;
for (uint32_t i = 0;; i )
{
v[i 1] = v[i] / 10u;
v[i] = v[i] % 10u;
if (i >= top && v[i 1] == 0)
{
top = i;
return;
}
}
}
void times2() {
for (uint32_t i = 0; i <= top; i )
v[i] *= 2;
if (( normalize_count) > Normalize_Max)
normalize();
}
};
void add(BigDecPower2& v1, const BigDecPower2& v2)
{
uint32_t max_top = v1.top > v2.top ? v1.top : v2.top;
for (uint32_t i = 0; i <= max_top; i )
v1.v[i] = v2.v[i];
if ( v1.normalize_count < v2.normalize_count)
v1.normalize_count = v2.normalize_count;
if (v1.normalize_count > v1.Normalize_Max)
v1.normalize();
}
void print_base(unsigned int n, int number_base)
{
int64_t ones = n-1;
int64_t zeros = n;
if (number_base ==2)
{
while (ones-- > 0)
cout << '1';
while (zeros-- > 0)
cout << '0';
}
else if (number_base == 16) {
int resid = (ones zeros) % 4;
if (resid == 0)
resid = 4;
cout << "~137F"[resid];
ones -= resid;
while ((ones -= 4) > 0)
cout << 'F';
cout << "8CEF"[ones 3];
zeros /= 4;
while (zeros--)
cout << '0';
}
else if (number_base == 10)
{
BigDecPower2 v_accum(40000u);
BigDecPower2 v_pwr(40000u); v_pwr.v[0] = 1;
for (uint32_t i = 0; i < n - 1; i )
{
add(v_accum, v_pwr);
v_pwr.times2();
}
for (uint32_t i = 0; i < n; i )
v_accum.times2();
v_accum.normalize();
for (uint32_t i = v_accum.top; i != -1; i--)
cout << static_cast<char>(v_accum.v[i] '0');
}
cout << '\n';
}
int main()
{
// calcs in about 3 seconds, outputs about 40k decimal chars
// print_base(0xffff, 10);
// Demo
for (int i = 1; i < 10; i )
{
print_base(i, 2);
print_base(i, 16);
print_base(i, 10);
cout << '\n';
}
}