PHP Maths Problem

[rich w]

Greetings to all!

I'm currently working on a permissions system for a CMS i'm building, but have hit a slight problem... maths :lol:

Take the following list:
1
2
4
8
16
32
etc...

Yep, they're all just doubling the previous value. Easy enough!


Now what I want to do is supply a number, let's say 11. I then need to find all the numbers in that list which when added together, produce that number. So in the case of 11, this would return 1, 2 and 8 (1 + 2 + 8 = 11).

Via a bit of googling, i've got the following code:

$mask = 5;
$return = array();
while ($mask > 0) {
for($i = 0, $n = 0; $i <= $mask; $i = 1 * pow(2, $n), $n++) {
$end = $i;
$return[] = $end;
}
$mask = $mask - $end;
}
sort($return);
However, it doesn't work very well... it returns
[0] => 0
[1] => 0
[2] => 1
[3] => 1
[4] => 2
[5] => 4

when it should return
[0] => 1
[1] => 4

Does anyone have any ideas on how to go about solving this problem? Any ideas, attempts etc would be appreciated! :D

[chaos]

Um, I think you lost me there, but I will try and clarify for myself. The range of possible values in your answer is the sequence of numbers created when you double the previous value assuming that the initial value is 1. <small sidenote to self: you don't actually have to use a series, but a sequence would work as well so long as you add one to the final sum> The user will input a number of their choosing assuming it is a positive integer, and this number will be passed onto a function. You are trying to write a function that will find the most efficient way to add the numbers that fall into your range so that their sum is the number the user inputted. Is this correct?

Oh, and in your example, I am assuming that "$mask" is the value the user will input? And, the problem is that it is returning a set of numbers whose sum is 1 greater than mask, and it's certainly not choosing a very efficient method of addition either. I'll post again once I look at it some more.

So, I just looked through the code, and it looks like there certainly isn't enough code there. I have an algorithm in mind for this problem, but only assuming my initial assumptions about your question are correct.

[rich w]

Yep you're spot on there. I reckon your description is much more easily understood than mine!

You're right about the efficiency as well... I've drawn up a table in Excel which shows the system storing 50 permissions... resulting in a 16 digit number. That could take some processing!

I've been thinking that binary could be the way... as it's the same pattern i'm using. There are operators in PHP to do left and right binary shifts... << and >>
I reckon that will be a good starting point for a long night for me!

[inimino]

How are integers stored in a binary computer?

Let's take the number 11, in binary, stored as the following byte:


0000 1011


Note the positions of the set bits (the ones) representing 2^0, 2^1, 2^3.

In binary arithmetic, each position represents a power of two. (Just like in decimal each represents a power of ten.) 8+2+1 isn't just something you can derive from 11, it's actually how it is stored. What you are trying to do is simply determine which bits are set in an integer variable. The way to do this is with bitmasks, and the bitwise operators such as &.

That should get you started in your reading.

[chaos]

So, you are saying that you are trying to condense the permissions numbers into one number that is much shorter, and this formula is supposed to do that? Or is this formula unrelated, and you still need that algorithm? Inimino is the guy to ask around here on this sort of thing, but I do like to keep my math skillz sharp during the summer when it's all going to mush...

To do what you were asking earlier, I would make something like the following (this isn't working PHP, just an example. I wish it did work, but unlike inimino here, I have a hard time just quickly writing up/testing stuff, but in the interest of time, I made up a decent example).

<?PHP
$mask = 5;
$return = array();
$final = array();
$set = 0;

for($i = 0, $n = 0; $i <= $mask; $i = 1 * pow(2, $n), $n++) {
$return[] = $i;
$set++;
}
sort($return);
for ($i = $set; $i >= 0; $i--) {
if ($return[$i - 1] + $current_total < $mask) {
$current_total = $current_total + $return[$i - 1];
$final[] = $return[$i - 1];
}
if ($current_total = $mask) {
break;
}
}
sort($final);
?>


Basically, what I was (trying, though I am not very good at PHP) is to put into a decent script my algorithm. You want to first go through all the possible doubles that fit into range, and stop once they are bigger than the expected number. Store all these numbers into an array, and then we go through this array and begin to try adding various combinations of those numbers from greatest to least (the most efficient way). Store what works, into a final array, and then your're golden. I can't come up with any examples where this wouldn't work, though I didn't really test it :) Just thinking out loud.

[rich w]

Thanks very much for that attempt, it gave me some fresh ideas. I noticed you were using powers, and followed the program through to see how it worked. From that, I tried combigning binary and powers, to excellent results :D


$mask = 11;
for ($i = 1; $mask > 0; $i <<= 1, $mask >>= 1)
{
if (($mask & 1) == 1)
{
$permissions[] = $i;
}
}
//$permissions contains 1, 2 and 8.


The << and >> operators take all the bits in the number (if you imagine it as binary) and move them one place to the left or right, which has the effect of multiplying or dividing by two (any remainder after the division is dropped).

Eg. 3 << 4 is the same as 3 * pow(2, 4).

Anyway, thanks very much for your time spent on this. It was the ideas that inspired me to get the final result! I think i'm going to have to write an article on user permissions at some point!

Cheers,

[inimino]

Looks good, Rich.

You could also do this:


$mask = 11;
for ($i = 1; $i < $mask; $i <<= 1)
{
if ($mask & $i)
{
$permissions[] = $i;
}
}
//$permissions contains 1, 2 and 8.


That might be insignificantly faster, and perhaps slightly more readable, and doesn't change the value of $mask.

I'm kind of curious to see how this snippet is used. What does $permissions get used for?

[rich w]

It's the basics of a really customisable and powerful open source CMS i'm building... the permission system is one of the beauties of it. It allows the administrator to create site wide permissions for anything they want.

Basically, a user or user group is assigned a number ($mask). This number contains details of all the permissions the user is allowed to do.

When the user first visits the site, PHP works out all these permissions and saves them to the user's session. On each page of the site, the permissions can be checked whether they exist in the array, to decide whether a user can or can't do something...

It just seemed like a really logical way of keeping the database size small, and cutting down on processing time for producing each page.

The good news is it all seems to be working so far! I'll definetely have to write an article on the subject, as it seems to be a really effective system :)

[chaos]

Thanks very much for that attempt, it gave me some fresh ideas. I noticed you were using powers, and followed the program through to see how it worked. From that, I tried combigning binary and powers, to excellent results :D


$mask = 11;
for ($i = 1; $mask > 0; $i <<= 1, $mask >>= 1)
{
if (($mask & 1) == 1)
{
$permissions[] = $i;
}
}
//$permissions contains 1, 2 and 8.


The << and >> operators take all the bits in the number (if you imagine it as binary) and move them one place to the left or right, which has the effect of multiplying or dividing by two (any remainder after the division is dropped).

Eg. 3 << 4 is the same as 3 * pow(2, 4).

Anyway, thanks very much for your time spent on this. It was the ideas that inspired me to get the final result! I think i'm going to have to write an article on user permissions at some point!

Cheers,

Well, I can't take too much credit for that script as the part you were looking at was actually pretty much the same as the one you were using before :lol: All I did was to add a second for statement which I had intended to come up with the most optimized results. Basically you're first for loop would put all the values that are less than the $mask into the output, without necessarily regarding the fact that the total sum will be greater than $mask. The second for loop I added would go through and find the smallest set of numbers needed to make $mask. I am glad though that you figured it out! Good luck with the CMS!

[inimino]

It's the basics of a really customisable and powerful open source CMS i'm building... the permission system is one of the beauties of it. It allows the administrator to create site wide permissions for anything they want.

That sounds like a fun project.

Basically, a user or user group is assigned a number ($mask). This number contains details of all the permissions the user is allowed to do.

Unix filesystem permissions are done this way, (although "mask" has a slightly different denotation in that context) and for similar reasons: space and time efficiency.

A filesystem permissions system must check the permissions before every file or directory read or write operation. Obviously, this has an impact on overall operating system performance, for example, running a simple program may open hundreds of files.

The way this is handled is by storing the permissions for a file in a single integer, where each bit represents one permission. Then permissions checks can be done against this value in just a single processor instruction.

When the user first visits the site, PHP works out all these permissions and saves them to the user's session. On each page of the site, the permissions can be checked whether they exist in the array, to decide whether a user can or can't do something...

You can optimize this even more (although it means doing away with the lovely code you just wrote ;)) by not creating the array, and simply keeping the integer around and directly checking the bits you care about. This saves the memory occupied by the array, the time of generating the array, and the time of accessing an array when you need to check permissions. Given that this is a CMS written in PHP, and not a filesystem layer written in C, these efficiency improvements will not be so critical, but it is still satisfying do it the right way, which is the most efficient way. It will also make your code cleaner and easier to read.

The way this is done is by defining constants for each bit so you can refer to them by name, for example, for some hypothetical permissions system you might have:

define("PERM_READ", 1);
define("PERM_WRITE", 2);
define("PERM_MODIFY", 4);
define("PERM_ADMIN", 8);

(In C header files, long sequences of #define directives with ascending powers of two are a very common sight.)

Then to check if a permission is set:

if ($user_perm & PERM_WRITE) { ... }

Set permission bit:

$user_perm |= PERM_WRITE;

Unset a bit:

$user_perm &= ~PERM_WRITE;

[rich w]

Sorry for the delay in replying guys, just been on camp for nearly a week... now i've recovered it's back to working on this CMS!

Although inimino's solution would produce a more efficient operation, the problem I can see is that the user can add, edit and delete permissions. Because they would be hardcoded into the PHP files, this could make it very difficult to code. This is the main reason why I decided to store all the permissions in the database. Your method does look a lot easier to read than mine as well :(

Anyway, i'll keep you posted on the CMS, it's becoming pretty powerful so it'll be interesting to see how popular it gets when it's released!