Factoring

Qfwfq · February 24, 2005

Cool it guys, what's the point of arguing about the so many different ways of allocating and handling structures and arrays in C/C++?

Here's a slightly tricky one:

int a = <expression>;
myFunc(1492, 2941) = a;

How was myFunc declared, for this to make sense? :cup:

Qfwfq · February 24, 2005

A question. Let N=(2^31)( 3^19)

How many Interger divisor of N^2 are less than N but do not divide N?

That's a more interesting question Kent. To square N, just double the exponents. The divisors of N square that don't divide N are the ones that have at least one greater exponent. They can be less than N by having other exponents small enough, e. g. 2^32. The ratio to N can be written in terms of the differences in the exponents, in the above example (2^32)/N = 2/(3^19) which is much less than 1.

It's a matter of comparing 2^a and 3^b which can be done by multiplying b by the base-2 logarithm of 3. Right now I can't fully work out how to compute the exact count, and for a general N, but I would follow on this path.

Hmm...... I have little patience to look through every post

Sure enough, you did not!

alexander · February 24, 2005

Oh, and data structures can have names, and where else would one allocate an array except in memory, and if you dynamically allocate an array wouldn't have a pointer anyway?

:cup:

no if you create an array via "int array[10];" you create an array named array with enough space reserved in memory for 10 integers, all with the same name (array). Really technically, it is a sort of pointer, but in reality it really isnt, a pointer is an integer that holds a value to the location of whatever it is pointing to in memory, be that class, function or an array or an array of classes, whatever, it differs from an array in that it only contains an adress to the memory location, thus differentiating in values that are passed. Take for example 2 functions, same name, one taking in an array, other taking in a pointer to an array. While the first fuction will have all the values of an array passed to it, second function has only a short int passed to it, making it that much faster, if you are passing a huge array, say 100x100 for example, instead of 10000 values passed, you will only have an int, but that int allows you to access those 10000 values almost as if you are using the array itself.

back to datastructures though, there are many really cool ways of doing things with arrays, here's a cool one for example:

//enumeration
enum Days { Mon, Tues, Wed, Thurs, Fri, Sat, Sun};
string day[Days]={"Monday", "Tuesday","Wednesday","Thursday","Friday","Saturday","Sunday"};
cout << day[Mon]<<"/n";

Kent · February 24, 2005

That's a more interesting question Kent. To square N, just double the exponents. The divisors of N square that don't divide N are the ones that have at least one greater exponent. They can be less than N by having other exponents small enough, e. g. 2^32. The ratio to N can be written in terms of the differences in the exponents, in the above example (2^32)/N = 2/(3^19) which is much less than 1.

It's a matter of comparing 2^a and 3^b which can be done by multiplying b by the base-2 logarithm of 3. Right now I can't fully work out how to compute the exact count, and for a general N, but I would follow on this path.

try to work throught it, and explain your solution. It is a neat question

Sure enough, you did not!

You are repeat every thing i am saying? What s the matter with you? I saw the first post, and that is all.

alexander · February 25, 2005

ok, final pogram:

#include <iostream>

using std::cout;
using std::cin;

int main()
{
int *number= new int;
for (number; number <= 150; number++)
{
	int numOfDivisors = 0;
	for (int divisor = 1; divisor <= number; divisor++)
	{
		if (number % divisor == 0)
			numOfDivisors++;
	}
//		cout << "n" << num << " has " << numOfDivisors << " divisors.";
	if (numOfDivisors % 2 != 0)
		cout << "nMailbox #" << number << " is closed.";
}
cout << "nnWork completenn"; 
       return 0;
}

but to find the amount of divisors do this:

#include <iostream>

using std::cout;
using std::cin;

int main()
{
int number=0, final=0;
       cout << "what number do you want to factor to?";
       cin >> final;
for (number; number <= final; number++)
{
	int numOfDivisors = 0;
	for (int divisor = 1; divisor <= number; divisor++)
	{
		if (number % divisor == 0)
			numOfDivisors++;
	}
	cout << "n" << num << " has " << numOfDivisors << " divisors.";
}
cout << "nnWork completenn"; 
       return 0;
}

no datastructures stuff anywhere, but a better algorithm for figuring out the final behavior :cup:

TeleMad · February 26, 2005

Cool it guys, what's the point of arguing about the so many different ways of allocating and handling structures and arrays in C/C++?

Here's a slightly tricky one:
int a = <expression>;
myFunc(1492, 2941) = a;
How was myFunc declared, for this to make sense? :cup:

I haven't programmed in C++ for a couple years, but to be an LVALUE, I'd guess myFunc was declared as having a return type of a reference to an int.

TeleMad · February 26, 2005

Telemad: Oh, and data structures can have names, and where else would one allocate an array except in memory, and if you dynamically allocate an array wouldn't have a pointer anyway?

:cup:

Uhm, YEAH!

alexander: no if you create an array via "int array[10];" you create an array named array with enough space reserved in memory for 10 integers, all with the same name (array).

And an array's name is a pointer, of the correct type, to the array's first element! Remember? That's why you can access the elements of an array either by the use of subscripts or pointer arithmetic. For example,

array[2] = 5;

is identical to

*(array + 2) = 5;

Also, note that you changed the topic from a dynamically allocated array (which uses the new operator) to talking about a array 'allocated' at compile time.

alexander: Really technically, it is a sort of pointer...

No "sort of" about it: an array's name is a pointer to its first element. So if you delcare an array, even in your switching to a non-dynamically allocated array, you still have a pointer.

And getting back to the original topic - the dynamically allocated array - you are automatically handed pointer because that's what the new operator returns.

So let's review the 3 things I said.

1) "Oh, and data structures can have names..."

This is a true statement.

2) " ... and where else would one allocate an array except in memory..."

Well? Of course any array that is allocated in allocated in memory.

3) " ... and if you dynamically allocate an array wouldn't [you] have a pointer anyway"

You'd definitely have the ability to use a pointer since the new operator returns a pointer.

So what exactly is your "Uhm, No!" about?

alexander: Take for example 2 functions, same name, one taking in an array, other taking in a pointer to an array. While the first fuction will have all the values of an array passed to it, second function has only a short int passed to it, making it that much faster, if you are passing a huge array, say 100x100 for example, instead of 10000 values passed, you will only have an int, but that int allows you to access those 10000 values almost as if you are using the array itself.

You're confused. Somewhere along the way you seem to have twisted what I said into something different.

Oh, and one can simply use EITHER the array name OR a pointer as a parameter in the function definition and get just a single pointer to the array, instead of trying to receive the whole thing by value.

It's like you are going out of you way to make something clumsy...worse yet, you're addressing something I never even mentioned.

Buffy · February 26, 2005

Boys, boys, boys...calm down. C, C++, Java and other relatives only pass base datatypes on the stack, which means that only a pointer is passed, unless you litterally reference every cell in the array in the argument list. It does not matter whether the function argument is declared as (int *array) or (int array[]), that name "array" is a pointer to the space in memory. You need a language like Pascal or Ada if you really want to pass a copy of the array on the stack, and even then, you need a "By Val" keyword. Language mavens will tell you this is one of the "weaknesses" of the C-family of languages.

Cheers,

Buffy

TeleMad · February 26, 2005

my original problem involves a guy who has a huge amount of mailboxes that are first all closed, then all he does is secod time when he passes by them, he opens every second mailbox, the third time he passes the mailboxes, he changes state of every third mailbox and so forth. I have to write a program to do this and give out the final result. ... oh and this is for the datastructures class, not elementary algebra, just to make it clear.

Sorry Alexander, but I think your whole approach is wrong. You are not modeling someone sequentially passing mailboxes and toggling their flags: you are doing math. The algorithm you end up with will work ONLY WITH THE CURRENT SPECIFICATION: it won't be flexible. And as anyone in the business knows, specifications change. So what happens if the instructor wants to change the specification a bit. What if s/he says that there are 1000 mailboxes but the person makes only 7 passes, or 11 passes, or 23 passes? How does your mathematical solution work then? What if s/he then changes it a bit more so that the person forgets to toggle the flags on pass 4? How does your mathematical solution work then?

The "dumb" way - the straightfoward modeling of the real world - that the rest of the class will probably implement will be easy to modify to fit these changing demands: yours won't.

And most of a programmer's time is spent MAINTAINING existing systems, not creating them. You should build your systems to be maintainable, predicting what future changes may be demanded.

PS: And I also think it's a bit unethical of you to try to elicit solutions from others if you are expecting to earn yourself a pat on the back from the instructor for thinking outside the box.

Qfwfq · February 28, 2005

Boys, boys, boys...calm down. C, C++, Java and other relatives only pass base datatypes on the stack, which means that only a pointer is passed

Not quite right Buffy, for C and C++, if you declare a parameter of type struct or class without a * or & the whole instance is copied onto the stack! Not so in Java, and you're right about arrays, but I don't think the boys' argument is just about passed parameters.

Telemad: Answer correct. I once heard about a University professor that was flunking a lot of students on that one!

alexander · February 28, 2005

ok, i see that there's been a lot of talk about me here, i really havent had time to reply, but thanks for your honestly and thoughtfullness in pointing out the obviouls flaws within the program.

first though

no if you create an array via "int array[10];" you create an array named array with enough space reserved in memory for 10 integers, all with the same name (array). Really technically, it is a sort of pointer, but in reality it really isnt, a pointer is an integer that holds a value to the location of whatever it is pointing to in memory, be that class, function or an array or an array of classes, whatever, it differs from an array in that it only contains an adress to the memory location, thus differentiating in values that are passed. Take for example 2 functions, same name, one taking in an array, other taking in a pointer to an array. While the first fuction will have all the values of an array passed to it, second function has only a short int passed to it, making it that much faster, if you are passing a huge array, say 100x100 for example, instead of 10000 values passed, you will only have an int, but that int allows you to access those 10000 values almost as if you are using the array itself.

thats what you get with over 2 days uptime on your body :eek: you just dont really think...

you are absolutely correct with pointing out the obvious, i should go and hit myself for such post... ok, back, but i think that you are wrong in saying that the solution is a dumb one, here's why:

1) factoring in 15 lines of code can prove quite challenging...

2) this solution modeled perfectly what was asked of it, there was no word on flexibility in the problem and making it not as flexible in first will ensure higher revenues later on when the company needs flexibility built into their software

3) it is a much faster approach to solving that particular problem, 5-7 years ago when the industry was still conserned with clock cycles this would have been considered the more correct solution (ofcourse i agree with the flexibility point, but given time it could be resolved)

Buffy · March 1, 2005

Not quite right Buffy, for C and C++, if you declare a parameter of type struct or class without a * or & the whole instance is copied onto the stack!

My goodness, you're right. Of course its not great coding practice except for recursion...

Cheers,

Buffy

typedef struct {  int x; } sst_type;
sst_type sst;

int callsst(sst_type s) {
printf("In the Func before change: %d", s.x);
s.y=111;
printf("In the Func before change: %d", s.x);
return s.y;
}

int main() {
sst.x = 888;
callsst(sst);
printf("After the Func before change: %d", sst.x);
return 0;
}

Qfwfq · March 1, 2005

not great coding practice...

Sure, it can be a pitfall, especially if you're accustomed to languages with non-automatic byval. Recursion isn't the only good case though, any time when you actually need an independent copy to modify. I've used it.

alexander · March 1, 2005

ooh, i almost forgot:

And I also think it's a bit unethical of you to try to elicit solutions from others if you are expecting to earn yourself a pat on the back from the instructor for thinking outside the box.

firstly i never said that i needed a pat in the back from anyone, secondly, me and my friend have worked on the solution for a few days, the effort was not all mine, so i dont claim it to be, thirdly we are all GNU Public license users, so i can use his code as much as i need/want to, and final and probably the biggest point why i find your above quote offensive is the question that some programmers cant answer, why reinvent the wheel? there is enough of that going on in the programming world already, so why give in and start rewriting code that has already been written, or come up with solutions that somebody else already solved and chances are did a better job than you or I will? I fully understand the way that logic works, I have also written or rather showed how to write the brute force solution to that same exact problem for another friend of mine, its not that i cant do it, i was just looking for a better or rather faster and more efficient way out. I might, if i have time today, build a class to do it both ways depending on the arguments passed, but i might not have the time to do so, i'll post it though, just for you Tele...

TeleMad · March 14, 2005

ok, back, but i think that you are wrong in saying that the solution is a dumb one, here's why:

1) factoring in 15 lines of code can prove quite challenging...

Determining how many factors a number has in 15 lines of code is quite easy.

By the way, switching to your math method, in very short time I came up with much more efficient algorithm for determing how many factors a number has than yours. Here's yours:

int numOfDivisors = 0;
for (int divisor = 1; divisor <= number; divisor++)
{
    if (number % divisor == 0)
         numOfDivisors++;
}

And here's my more efficient method:

int numOfDivisors = 2;
if (number == 1)
    numOfDivisors = 1;
else
{
    for (int divisor = 2; (divisor * divisor) <= number; ++divisor)
    {
         if (divisor * divisor == number)
              numOfDivisors++;
         else if (number % divisor == 0)
              numOfDivisors += 2;
    }
}

Looking at the loops, which constitute most of instructions executed, and taking the worst possible case (the usual method for comparing algorithms), and using n to represent number, yours requires 2n instructions to be executed while mine requires only 3[n^(1/2) - 1]. My algorithm is theoretically more efficient than yours for all n.

alexander: 2) this solution modeled perfectly what was asked of it, there was no word on flexibility in the problem ...

And when clients or superiors give you specifications for a new system they aren't going tell you that they're going to change it a dozen times over the next few years, but they likely will. What you did might be fine for class, but it's poor for the real world.

alexander: ... and making it not as flexible in first will ensure higher revenues later on when the company needs flexibility built into their software

I sure hope when you try that unethical practice in real life your clients/superiors don't find out!

alexander: 3) it is a much faster approach to solving that particular problem...

Actually, my above algorithm is much more efficient than yours.

Further, look how long it took you to figure out how to do it the 'wrong' way ... longer than if you just did it the straightforward way.

Let's sum up.

1) it took you longer to write the code your way

2) your solution was less flexible than the straightfoward way

3) your final algorithm was less efficient than what I quickly whipped up

TeleMad · March 20, 2005

TeleMad: Here's yours:
int numOfDivisors = 0;
for (int divisor = 1; divisor <= number; divisor++)
{
    if (number % divisor == 0)
         numOfDivisors++;
}
And here's my more efficient method:
int numOfDivisors = 2;
if (number == 1)
    numOfDivisors = 1;
else
{
    for (int divisor = 2; (divisor * divisor) <= number; ++divisor)
    {
         if (divisor * divisor == number)
              numOfDivisors++;
         else if (number % divisor == 0)
              numOfDivisors += 2;
    }
}
Looking at the loops, which constitute most of instructions executed, and taking the worst possible case (the usual method for comparing algorithms), and using n to represent number, yours requires 2n instructions to be executed while mine requires only 3[n^(1/2) - 1]. My algorithm is theoretically more efficient than yours for all n.

It's easy to see that my algorithm, which stops iterating through the loop at about n^(1/2) instead of going all the way to n like alexander's does, is far more efficient for large values of n because the bulk of execution would be spent in the loop. But my version has more lines of non-loop code so maybe for small n mine will have to execute more code. I didn't think so but was too busy to actually check. I spent a couple minutes desk-check comparing the two and found that mine is more efficient for small n also. Here are the quickly determined values.

n = 1

mine = 3 statements executed

alexander = 6 statements executed

n = 2

mine = 4 statements executed

alexander = 10 statements executed

n = 3

mine = 4 statements executed

alexander = 12 statements executed

n = 4

mine = 8 statements executed

alexander = 16 statements executed

n = 5

mine = 8 statements executed

alexander = 18 statements executed

Qfwfq · April 7, 2005

Looking at the loops, which constitute most of instructions executed, and taking the worst possible case (the usual method for comparing algorithms)...

I don't want to say your algorithm is less efficient than the simpler one but worst case isn't always the best performance comparison between algorithms, performance depends on many things. Apart from complex issues like cache misses and page faults or whatnot, even just considering number of steps, I think Quicksort would lose even against the slow Bubblesort, in a worst case based estimate, but an estimate considering statistics gives it its name.

I repeat that having a list of primes enables a much quicker method and, if you need to do it for various numbers, the list of primes needn't be re-computed for each number.

Here is an efficient implementation of Eratosthene's sieve that I wrote years ago and recently re-adapted for a few recent uses. It can execute as needed; if you first call it with a low value in the parameter it will do part of the work, and continue when you call it with a higher value. Pass it a uLong containing 999810, which isn't prime, when it returns the variable will contain 999853 which is prime.

Change the allocation scheme if necessary, but with care, don't just change the #define.

#include "stdio.h"
#define lhFF  (0xFFFFFFFF)

typedef unsigned long uLong;

// Copyleft Qfwfq, all rights reversed.

bool nextPrime(uLong& n){
static uLong numFlgs = 0x4000000, k = 0x7FFFFFFF, maxPrm = 1,* m_Flgs = 0,
  I = 0, i = 1, J, j, Q, q, dwi, dwj, dwq, maski = 2, maskj;
if(n <= 2){
 n = 2;
 return true;
}
(n == maxPrm)return true;
while(!m_Flgs){
 if(m_Flgs = new uLong[numFlgs]){
  for(uLong ii = 0; ii < numFlgs; ii++)m_Flgs[ii] = lhFF;
  break;
 }
 fprintf(stderr, " couldn't allocate %u bytes!nttype in a lower number:n", numFlgs << 2);
 scanf("%u", &k);
 numFlgs = k >> 2;
 (k & 3) && (numFlgs++, (k &= ~3), k += 4);
 (k <<= 3)--;
}
if(n < maxPrm){
 uLong ii = (n >> 1), dwii, maskii = 1 << (ii%32), II = ii >> 5, max = (maxPrm >> 1);
 for(; ii < max; II++, maskii = 1){
  dwii = m_Flgs[iI];
  for(; maskii && ii <= lhFF; ii++, maskii <<= 1){//		ii = 32II + ii%32
   if(dwii & maskii){
    n = 1 + (ii << 1);
    return true;
   }
  }
 }
}
uLong in = n >> 1;
for(; i <= k; I++, maski = 1){
 dwi = m_Flgs[i];
 for(; maski && i <= k; i++, maski <<= 1){//		i = 32I + i%32
  if(dwi & maski){
   if(i >= in){
    n = maxPrm = 1 + (i << 1);
    return true;
   }
   for(j = (k - i)/((i << 1) + 1), J = (j >> 5), maskj = 1 << (j & 0x1F)
; j >= i; J--, maskj = 0x80000000){
    dwj = m_Flgs[J];
    for(; maskj && j >= i; j--, maskj >>= 1)//		j = 32J + j%32
     if(dwj & maskj){
      q = ((i*j) << 1) + i + j;
      m_Flgs[Q = (q >> 5)] &= dwq = ~(1 << (q & 0x1F));
      (Q == I) && (dwi &= dwq);
     }
   }
  }
 }
}
return false;
}

Sign In

Factoring

Recommended Posts

Link to comment

Share on other sites

Top Posters In This Topic

Popular Days

Top Posters In This Topic

Popular Days

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Join the conversation