C++ Challenge - Page 2

[JRM]

Why not just use mathematical functions to solve this?? :)

Basically we calculate numbe of digits with log10 and round upwards. Then we sort of devide the number into two parts, one with all digits up to start+count and same number but with everything between start and start+count canceled to zero. Now we can simply subtract these two numbers and get the digits we were after. Fast and efficient :)

It works!
Personally, if I was giving out the awards, I think I'd give to YOU!
What I like about it is that you kept it consistantly numeric without resorting to a string. Very nice...

I gave myself the same personal challange but was thinking along the (very convoluted) lines of outptting the long in some base, say hex, and then using a recursive algorithm to pull one digit at a time. I failed dismally...

I'm just a beginner.
I hope you are a professional at this so I don't feel so bad...

[Rashakil Fol]

Okay, I'll put my more-polished entry up, for category three. I'm assuming valid input, because it's category three. It's pretty much my previous version with a bugfix. For example, it runs 180 times faster than pixl's version in the test program I wrote, after I removed the error checking from pixl's version and put the arguments in the right order, when compiling with g++ -O3. Also it works properly when x is a power of ten (pixl's doesn't).

unsigned long extract_digits (unsigned long x, size_t n, size_t i) {
  static const unsigned long tenpows[]
    = {1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};

  size_t len;
  if (x < 1000) {
    len = 1 + (x >= 10) + (x >= 100);
  }
  else {
    if (x < 1000000) {
      len = 4 + (x >= 10000) + (x >= 100000);
    }
    else {
      
      if (x < 100000000) {
	len = 7 + (x >= 10000000);
      }
      else {
	len = 9 + (x >= 1000000000);
	if (n == 10) {
	  return x;
	}
      }
    }
  }

  x = x / (tenpows[len - i - n]);
  
  return (x % tenpows[n]);
}

[pixl]

Okay, I'll put my more-polished entry up, for category three....

Nice idea. Though not scalable to systems that might use larger longs. Also, why are you doing that ugly bruteforce length calculation mess? Use ceil(log10(x))! It makes that code twice as fast too!

static unsigned long *tenpows=0;
class _spowslong{
    public:
    _spowslong(){
        size_t dn=(size_t)ceil(log10(ULONG_MAX));
        tenpows=new unsigned long[dn];
        for(size_t c=0;c<dn;c++){
            tenpows[c]=(unsigned long)ceil(pow(10,c));
        }
    }
};
//automatic initialisation of tenpows array
static _spowslong dummy;

unsigned long extract_digits (unsigned long x, size_t n, size_t i) {
    size_t len;
    len=(size_t)(ceil(log10(x)));
    if(n>len||(n+i)>len)
        throw (const char*)("Invalid value for start and end!");
    x = x / (tenpows[len - i - n]);
    return (x % tenpows[i]);
}

A little more scalable version :)

[~s.o.s~]

Unless put through some rigorous testing and profiling tools, the performance difference between the algorithms proposed so far is insignificant.

[thekashyap]

Is the code expected to be HW/compiler independent ?

> Is the code expected to be HW/compiler independent ?
Standard C++ is always compiler independent.

That's purely from input interpretation pov. Not the output it generates.
1. I think others have pointed out about the size of the long.
2. A compiler usually supports options to generate hardware dependent optimized binary (which uses all the goodie instructions supported by that hardware).

Finally if one wants "expert level optimization" such questions would always come up. :).

I was thinking on lines of doing some bit-wise manipulation on the memory where input long is stored. But this would strictly depend on the way a long is represented/stored in memory which is OS dependent. So the question...

Just one comment on the solutions that have been posted.
Very nicely written stuff.. :)

~s.o.s~'s code line 16-18

char* output = new char[MAX_SIZE];
memset(output, '\0', MAX_SIZE); //necessary to wipe the junk
strncpy(output, input + i, n);

can be changed to just put a single '\0' at end
and change output to a static var (would help in multiple calls):

static char* output = new char[MAX_SIZE];
strncpy(output, input + i, n);
output[n-i+1] = '\0' ; //or output[n-i] = '\0' ;, whichever is correct. :)

[~s.o.s~]

I can fairly bet that the zero initialization done when declaring static variables internally uses memset to achieve its objective. And I really wonder how making 'output' a static variable would help between function calls. :-)

[underjack]

And I really wonder how making 'output' a static variable would help between function calls. :-)

Without static, each time the function is called, output will be allocated, then deallocated before the function returns. Making it static means that it is only allocated once, and you don't pay the allocation/deallocation cost when you call the function.

[~s.o.s~]

Thanks 'underJack' but I guess you missed my smiley at the end. ;-)

[Rashakil Fol]

can be changed to just put a single '\0' at end
and change output to a static var (would help in multiple calls):

static char* output = new char[MAX_SIZE];
strncpy(output, input + i, n);
output[n-i+1] = '\0' ; //or output[n-i] = '\0' ;, whichever is correct. :)

There's no point in making a static char* pointing somewhere else in memory. You might as well just use space on the stack.

char output[MAX_SIZE];
...

[thekashyap]

There's no point in making a static char* pointing somewhere else in memory. You might as well just use space on the stack.

The obvious question would be WHY ?!

Given that you have a spectecular aura about, I'm sure you know that in case of static type var = new type() ; memory is allocated only once as stmt is executed only once and in type arr[size_t] ; , everytime.

[Rashakil Fol]

The obvious question would be WHY ?!

Given that you have a spectecular aura about, I'm sure you know that in case of static type var = new type() ; memory is allocated only once as stmt is executed only once and in type arr[size_t] ; , everytime.

The statement char output[MAX_SIZE]; takes exactly zero instructions to execute...

Use ceil(log10(x))! It makes that code twice as fast too!

Not on my computer.

[pixl]

Not on my computer.

That is nonsense. 10-logarithm always returns a number that is between numdigits-1 and numdigits. You can test it with simple windows calculator if you don't belive me. Also libc function log() is natural log and not log of 10, maybe you used it instead of log10() ;)

[underjack]

The statement char output[MAX_SIZE]; takes exactly zero instructions to execute...

That is a very naïve assumption. char output[MAX_SIZE]; doesn't directly compile to any instructions where it appears, but if it appears inside any function (including main), it declares an automatic object, which is created on the heap (aka free store) every time the function is called. To quote The C++ Programming Language 3rd Ed by Bjarne Stroustrup, page 145:

A local variable is initialized when the thread of execution reaches its definition. By default this happens in every call of the function and each invocation of the function has its own copy of the variable.

So every time you call the function, the computer must spend clock cycles to set aside unique space on the heap for all automatic variables in the function. Using char * output = new char[MAX_SIZE]; and delete[] char; has the exact same effect. Both use the heap, only difference is that with new , the allocation takes place when new is encountered in the function, and without, the allocations happens when the function is called.

[Rashakil Fol]

You don't know what you're talking about; the space gets allocated on the stack, not the heap, and it is allocated implicitly. chars don't get initialized. If you disagree, go compile a function with char output[20]; inside it and show us the assembly language instructions that allocate the space on the heap.

[Infarction]

As Rashakil says, when you have a stack allocated variable, the stack pointer will be incremented to account for it at the beginning of the function. This is much different from allocating on the heap, which has its own algorithms to compute where to allocate the space. And the operation of incrementing the stack pointer will happen each time the function is called anyways, whether you use a stack-allocated array or a heap allocated one. The heap operation would likely be much slower.

[JRM]

As a new C++ programmer, i want to challange myself to get a feel for using it in a creative way.

I discovered yet another way to accomlish the task. My first attempts crashed and burned miserably. I didn't want to leave it at that.

I have "borrowed" some ideas from prevous postings, yet the implementation is different with a couple of my own twists.

Sorry if i'm "beating a dead horse", but i want your comments and opinions to improve my skill (or lack thereof).

#include <iostream>
#include <math.h>
#include <stdexcept>
using namespace std;

unsigned long extract_digits ( unsigned long x, size_t n, size_t i )
{

        int z=0, c=x;
        while (c > 1)//get # of places
        {
                c = c/10;
               ++z;
        }

        if (n==0 || (n+i)>z) //test range
                throw runtime_error("parameters out of range");

        unsigned long a = (pow(10,(z-i)));
        unsigned long m = x % a;//get msd digits of interest

        m= m /(pow(10,(z-i)-n));//trim lsd's
        return m;
};

int main()
{
unsigned long result = extract_digits (3459812,3,2);
cout << result << endl;

return 0;
}

[Bench]

Nothing serious, just a couple of nitpicks -

#include <iostream>
#include <math.h>

Since this is C++, change that to #include <cmath>

unsigned long extract_digits ( unsigned long x, size_t n, size_t i )
{

        int z=0, c=x;

'x' is an unsigned long - don't take the risk that int and unsigned long are a different size, keep 'c' as an unsigned long too.

[ivailosp]

#include <iostream>
#include <stdexcept>
using namespace std;

size_t digit(unsigned long x) {
	size_t cnt = 0;
	while (x) {
		x = x/10;
		++cnt;
	}
	return cnt;
}

size_t pow_10(unsigned int x) {
	if (x == 0) {
		return 0;
	}
	unsigned int tmp = 10;
	while (x-1) {
		tmp*=10;
		--x;
	}
	return tmp;
}

unsigned long extract_digits(unsigned long x, size_t n, size_t i) {
	size_t z = digit(x);
	if (n==0 || (n+i)>z)
		throw runtime_error("parameters out of range");
	return x % pow_10(z-i) /pow_10((z-i)-n);
}

int main() {
	try {
		cout << extract_digits(3459812, 3, 2) << endl;
	}
	catch(runtime_error x) {
		cerr << x.what();
	}
	return 0;
}