Jump to content
Search In
  • More options...
Find results that contain...
Find results in...

Problem with function

erikpc43
 Share

Hello,

I have a problem with this function in picture. The function first finds the biggest 2 exponent of given number. So in this case is 2^4 which equals to 16. Then takes this number and subtract it from the given number which in this case is 22. And then again finds the biggest 2 exponent. So 22-16 is 6 and it finds 4 and again 6-4 is 2 and it finds 2. And it also add all numbers to list. So the function returns (16, 4, 2). This works just fine if you don't try larger numbers than 22, like the one in second pic, its to much to hadle and it takes too much time then. How could i fix the problem?

1.PNG

2.PNG

Link to comment
Share on other sites

Link to post
Share on other sites

You should look in recursion and it will likely be faster than a while loop.

                     ¸„»°'´¸„»°'´ Vorticalbox `'°«„¸`'°«„¸
`'°«„¸¸„»°'´¸„»°'´`'°«„¸Scientia Potentia est  ¸„»°'´`'°«„¸`'°«„¸¸„»°'´

Link to comment
Share on other sites

Link to post
Share on other sites

I don't even understand what the problem is , maybe I'm thick but the text of the problem is not clear to me.

Can you give a practical example with some real smaller numbers?

Link to comment
Share on other sites

Link to post
Share on other sites

1 minute ago, mariushm said:

I don't even understand what the problem is , maybe I'm thick but the text of the problem is not clear to me.

Can you give a practical example with some real smaller numbers?

if you enter number 22 it gives back a list [16, 4, 2]

if you enter 42 it gives back [32, 8, 2]

if you enter  10 it gives back    [8, 2]

I hope you get the point.

 

Link to comment
Share on other sites

Link to post
Share on other sites

So this (more or less) ?

 

<?php

function dostuff($number) {
	if ($number < 2 ) {
		echo ' '.$number;
		return;
	}
	$x = intval(floor(sqrt($number)));
	$y = pow(2,$x);
	while ($y > $number) {
		$x--;
		$y = pow(2,$x);
	}
	echo ' '.$y;
	dostuff($number-$y);
	echo "\n";
}

dostuff(22);
dostuff(42);
dostuff(10);

?>
d:\Programs\php7>php test.php
 16 4 2 0


 32 8 2 0


 8 2 0

 

// the function is recursive, the last 0 is in case you enter odd numbers like 21 or 43 ... I guess you could test if number is odd or even at the start, and of course instead of printing on screen you can put the numbers in an array either a global one or simply by returning each value and then flipping the array around if needed

 

// edit: thanks to wanderingfool2 below for reminding me,  using log instead of sqrt would make more sense in the code above... but in this particular case big shifting would be the fastest and easiest. 

Link to comment
Share on other sites

Link to post
Share on other sites

Or even cheaper, depending on numbers:

 

<?php 
function usingdecbin($number) {
	$binary = decbin($number); //converts number into string of 1s and 0s
	$j = 1;
	for ($i=strlen($binary)-1;$i--;$i>0) {
		$digit = substr($binary,$i,1);  // get n'th char from string
		if ($digit=='1') {
			echo ' '.pow(2,$j);
		} 
		$j++;
	}
	echo "\n";
}
usingdecbin(22);
usingdecbin(42);
usingdecbin(10);

?>

output is :

 

 2 4 16
 2 8 32
 2 8

You can just flip the array when you're done.

 

 

Or just use bit shift operations :

 

<?php
function usingshift($number) {
	$x = $number;
	$j = 0;
	while ($x > 0) {
		if ($x & 1) echo ' '.pow(2,$j);
		$j++;
		$x = $x >> 1;
	}
	echo "\n";
}

usingshift(22);
usingshift(42);
usingshift(10);
?>

Same crap, flip the array if you need the values the other way, or use left shifts but you'll need to know how many bytes the variable is stored in and it's more messy... but doable.

 

Link to comment
Share on other sites

Link to post
Share on other sites

I can't really say why yours doesn't work, I haven't really looked at the code (only at a glance).  My thought would be that your input is such a large number that it is overflowing the maximum value (e.g. integers are 2^63 - 1 or something like that)

 

May I point out something though, you can solve this problem by exploiting math.  Your goal is to initially find 2^x = some defined number; where x is an integer.  If you solve for x (including real numbers), and just floor x, you get the largest number.

 

e.g. some defined number 22;  Math.log(22, 2) = 4.459.  Flooring x, you get 4.  2^4 = 16.  There is your first number.

 

Actually it can be compressed to something like

//So doing pseudo code

func findMaxPower2(x)
	return 2 ^ Floor(Math.log(x,2))
    
func findAllMaxPower2(x)
	string = ""
    while(x > 0)
    	maxPower = findMaxPower2(x)
        x = x - maxPower
    	string = string + maxPower

 

*Edit

I read through your code now and found the reason your code takes forever consider these lines of code

for c in range(0, n + 1):
	if (2 ** c) <= n:
    	g = 2 ** c

This loops does what it was intending to do, but there is a fatal flaw when the number is large.  Consider n = 2 ** 100 = 1267650600228229401496703205376...notice the issue?  Your loop is going from 0 to 1267650600228229401496703205376.  The thing is when you hit c = 100, you will always get the 2 ** c <= n evaluating to false...but it still has to iterate c through another...well a freakishly large amount of numbers.  You want to put an else statement, and break out of that loop once g is found  (look up "python break").

 

I do like that you didn't use recursion (yes, it can make certain bits of coding harder or less pretty...but you don't risk overflowing your stack).  [razbij(2 ** 100000000 - 1) would break an recursive implementation of this].  The only critique I have of your code though, if you need to plan out the flow better.

 

From what I can tell, your first for statement could be completely eliminated by just moving 2 of the lines down below a for loop

e.g.

s=[]
while n>0:
	for c in range(0, n + 1): [You are looping a lot here when n = 2**1000000]
    	if (2 ** c) <= n:
        	g = 2 ** c
    s.append(g) [By moving these down, you don't need the first for loop].  You 
    n = n - g
return s

Anyways, hope this gives you a bit of insight into programming.  When you get stuck, a good approach is to put in the number that breaks your code, and trying to work out what your code is going with the number.

Edited by wanderingfool2
Found the reason his code messed up

3735928559 - Beware of the dead beef

Link to comment
Share on other sites

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share


×