Algorithms

Algorithm needed to find a point on A4 size plane

17-Nov-15 18:00

You have a set of data, and you search which subset will match a criteria.
This is a classical problem, I am not sure there is a name to this problem, or as mentioned in previous answer, it is related to the coin change problem.

Patrice

“Everything should be made as simple as possible, but no simpler.” Albert Einstein

Hash table load factor

Member 1180386012-Nov-15 13:04

Member 11803860

12-Nov-15 13:04

Hi.

I was recently interested in literature regarding what a good hash table load factor is for rehashing. Wikipedia mentions 0,7, 0,75 and 2/3, but with no explanation as to why performance degrades at these numbers.

The problem intrigued me, and I came to the conclusion that, mathematically speaking, the load factor threshold is at exactly log 2 (~0,7), which I found rather beautiful in it's own way.

I am posting this in case somebody else finds it interesting as I could not find any reference to a similar solution. Please also reply if you find any errors.

---------------------------------------

Chaining can be avoided and branch prediction exploited by predicting if a bucket is empty or not. A bucket is probably empty if the probability of it being empty exceeds 0,5.

Let s represent the size and n the number of keys added. Using the binomial theorem, the probability of a bucket being empty is:

P(0) = C(n, 0) * (1/s)^0 * (1 - 1/s)^(n - 0).

Thus, a bucket is probably empty if there are less than

log(2)/log(s/(s - 1)) keys.

As s reaches infinity and if the number of keys added is such that P(0) = 0,5, then n/s approaches log(2) rapidly:

lim (log(2)/log(s/(s - 1)))/s as s -> infinity = log(2) ~ 0,7.

Member 1213438812-Nov-15 3:45

Member 12134388

12-Nov-15 3:45

Distance given to a point on plane of A4 size. How to find X, Y if L1 and L2 (distances are given) ?

here is a link to image : http://s11.postimg.org/wymbahpxv/Xand_Y.png[^]

X1=55mm

Any ideas ?

Re: Algorithm needed to find a point on A4 size plane

Richard Deeming12-Nov-15 4:05

Richard Deeming

12-Nov-15 4:05

Split the larger triangle into two right-angled triangles, and apply Pythagoras:

<br />
L1² = x² + y²<br />
L2² = (X1 - x)² + y² = X1² - 2·X1·x + x² + y²<br />
<br />
L2² - L1² = X1² - 2·X1·x<br />
2·X1·x = X1² - L2² + L1²<br />
<br />
x = (X1² - L2² + L1²) / 2·X1<br />
<br />
y = ± √(L1² - x²)<br />

NB: there will be two solutions - one with a positive value for y, and one with a negative value.

"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer

Re: Algorithm needed to find a point on A4 size plane

Chris Maunder12-Nov-15 4:15

Chris Maunder

12-Nov-15 4:15

Use Pythagoras.

Let Pen tip = P. We know L1, L2, X1.

Define line segments R1 -> P = L1, R1 -> x = A, (x,0) -> P = B.

A² + B² = L1²

We know the length of A is X, since it's (0,0) -> (x,0), and we know length of B is y, since it's (x,0) to (x,y)

x² + y² = L1²

Let R2 -> P = L2, x -> R2 = C

B² + C² = L2²

A + C = X1 => C = X1 - A

So we have

x² + y² = L1²
y² + (X1 - x)² = L2²

Solve these and you get x and y

cheers
Chris Maunder

Fastest way to count nested loops

Member 113783027-Nov-15 2:32

7-Nov-15 2:32

Im inputing three numbers of users choice
number 1
number 2
final number

what i want to find out is , how many combinations of number 1 and number 2 would result in final number = number1 *x + number2*y = final number.

I am using nested loops

Objective-C

int i;
int j;
long long int pocet=0; // the numbers of combination
long long int one; // first number inputed by user
long long int two; // second number inputed by user
long long int last; // final number inputed by user - wanted result
long long int one_max;
long long int two_max;
long long int add=1; //for incrementing loops
long long int reduc=1; // for decrementing loops

if((one%2==0) && (two%2==0)){
        if(one>two){
            add=two/2;
            reduc=one/2;
    }
}
one_max=last/one;
two_max=last/two;
for(i=0;i<=one_max;i+=add){
    for(j=two_max;j>=0;j-=reduc){
        long long int tmp_one=(one*i);
        long long int tmp_two=(two*j);
            if(tmp_one+tmp_two==last){
                two_max=j;
                pocet++;
        }
    }
}

if i input these numbers
one = 10;
two = 13;
final =100;
the only possible combination of first two numbers to result in final number is
10 * 10 + 13 * 0

modified 7-Nov-15 11:37am.

Patrice T7-Nov-15 4:57

7-Nov-15 4:57

First of all, I fear your code don't work or is not complete.

Patrice

“Everything should be made as simple as possible, but no simpler.” Albert Einstein

Member 113783027-Nov-15 5:02

7-Nov-15 5:02

this is not full code , its just half pseudo code for illustrating my problem , i can provide full code if it helps

PIEBALDconsult7-Nov-15 5:18

PIEBALDconsult

7-Nov-15 5:18

If it's pseudo code, ho wdo you know it runs slow?

Member 113783027-Nov-15 5:36

7-Nov-15 5:36

i have updated my question , i wrote actual code which does works slow

Patrice T7-Nov-15 7:51

7-Nov-15 7:51

You should consider this

C++

long long int MyFunc (long long int one, long long int two, long long int last) {
	// one; // first number inputed by user
	// two; // second number inputed by user
	// int last; // final number inputed by user - wanted result
	
	int i;
	int j;
	long long int pocet=0; // the numbers of combination
	long long int one_max;
	long long int two_max;
	long long int add=1; //for incrementing loops
	long long int reduc=1; // for decrementing loops

	if((one%2==0) && (two%2==0)){
		if(one>two){
			add=two/2;
			reduc=one/2;
		}
	}
	one_max=last/one;
	two_max=last/two;
	for(i=0;i<=one_max;i+=add){
		for(j=two_max;j>=0;j-=reduc){
			long long int tmp_one=(one*i);
			long long int tmp_two=(two*j);
			if(tmp_one+tmp_two==last){
				two_max=j;
				pocet++;
			}
		}
	}
	return pocet;
}

as the source code to provide. Because we can't use your source code as is. In the form of a function, we can do test without changing a single line in this code.

First remark: using int for i and j may be short and should be replaced with long long int to match other variables.

Patrice

“Everything should be made as simple as possible, but no simpler.” Albert Einstein

Patrice T7-Nov-15 8:16

7-Nov-15 8:16

Here is code with first batch of changes. the code is changed to a function for practical reasons.

C++

long long int MyFunc (long long int one, long long int two, long long int last) {
	// one; // first number inputed by user
	// two; // second number inputed by user
	// int last; // final number inputed by user - wanted result
	
	// Question: How many (i,j) pairs (as positive integers) will verify
	// one*i+ two*j = last (constant part is on right)
	
	long long int i;
	long long int j;
	long long int pocet=0; // the numbers of combination
	
	for(i=0;i*one <=last;i++){
		// two*j = last - one*i (constant part is on right)
		// j = (last - one*i) / two (constant part is on right)
		if ((last - one*i )% two == 0) { // integer ?
			// solution
			j= (last - one*i) / two;
			pocet++;
		}
	}
	return pocet;
}

I just stick to the problem here.
I just take advantage of mathematics to change the equation as i is known. This should already improve the runtime.

Patrice

“Everything should be made as simple as possible, but no simpler.” Albert Einstein

Member 113783027-Nov-15 8:27

7-Nov-15 8:27

thanks for reply , i have also improved my code , but both , my and yours fail to be fast and calculate the number of combinatiosn when big numbers such as
5098109
25279297
36821491225502191
are inputed

Patrice T7-Nov-15 8:52

7-Nov-15 8:52

If you compare speed of both solutions with smaller values, mine should consistently faster the yours.

Patrice

“Everything should be made as simple as possible, but no simpler.” Albert Einstein

Member 113783027-Nov-15 9:08

7-Nov-15 9:08

yes no doubt about that , but both takes very long time to calculate numbers with big values such as i posted earlier

Patrice T7-Nov-15 9:19

7-Nov-15 9:19

To go further, change the code to print each solution in order and look at changes between solutions.
Try 3, 4, 150
Try 3, 4, 151
Try 3, 4, 153

And look at each set of answer, you should see a repeating patern. This what Harold is speaking about in http://www.codeproject.com/Messages/5156686/Re-Fastest-way-to-count-nested-loops.aspx[^]

And when you have a repeating pattern, you can know very fast the number of solutions without loop at all.

Patrice

“Everything should be made as simple as possible, but no simpler.” Albert Einstein

harold aptroot7-Nov-15 5:20

harold aptroot

7-Nov-15 5:20

That looks like Bézout's identity[^], the result depends on what algebraic structure you want to use, which is a bit unclear here. What size of integer do you want to consider?

You can see there what form the pairs of (i,j) take if they are solutions (called (x,y) on the wiki page). x increments in steps of b/gcd(a,b) and y decrements in steps of a/gcd(a,b). k can also go negative though. The problem then is counting how many of those things are in the valid range of your integer type. It has some weird edge cases but obviously you can do it without counting every possibility explicitly.