text:
Prize Payout Calculator Help

btaylor

New member
Hi all,
I am a programmer and in one of my projects I need a cash payout calculator based on upper and lower minimums and variable input.

Here are the variables:
Total amount to payout
Total number of payouts
Set minimum first place payout
Set minimum last payout
"K" to vary the slope of the curve

Example
Total amount to payout is 10000.
Payout is for 15 places.
1st places is guaranteed 4000.
Last payout (15) is 100.

I had someone help "many" years ago, but the total amount paid out was more than the size of the payout pool. Here is the code:

( ^ ) operator is for exponent
K = inK (inK is the K value to modify the slope)
N = pay_places (N=number of places to pay out)
AA = last_pay (AA=base prize minimum)
Z = max_pay (Z=top prize minimum)
D = pool (D=total payout)
Sum = 0
F = Z / AA
BB = F ^ (1 / ((N - 1) ^ K))

loop I = 0 TO N - 1
Sum = Sum + AA * BB ^ (I ^ K)
end

NewSum = 0

loop I = N - 1 TO 0 by -1
NewSum = NewSum + AA * BB ^ (I ^ K) * D / Sum
recommend = AA * BB ^ (I ^ K) (This adds up high)
pay_out = round((AA * BB ^ (I ^ K)),1) (but correctly sets hi and lo bounds)
.
. (more code to write out data)
.
end

Thanks in advance for any assistance
Bob

Last edited:

Klaas van Aarsen

MHB Seeker
Staff member
Hi all,
I am a programmer and in one of my projects I need a cash payout calculator based on upper and lower minimums and variable input.

Here are the variables:
Total amount to payout
Total number of payouts
Set minimum first place payout
Set minimum last payout
"K" to vary the slope of the curve

Example
Total amount to payout is 10000.
Payout is for 15 places.
1st places is guaranteed 4000.
Last payout (15) is 100.

I had someone help "many" years ago, but the total amount paid out was more than the size of the payout pool. Here is the code:

( ^ ) operator is for exponent
K = inK (inK is the K value to modify the slope)
N = pay_places (N=number of places to pay out)
AA = last_pay (AA=base prize minimum)
Z = max_pay (Z=top prize minimum)
D = pool (D=total payout)
Sum = 0
F = Z / AA
BB = F ^ (1 / ((N - 1) ^ K))

loop I = 0 TO N - 1
Sum = Sum + AA * BB ^ (I ^ K)
end

NewSum = 0

loop I = N - 1 TO 0 by -1
NewSum = NewSum + AA * BB ^ (I ^ K) * D / Sum
recommend = AA * BB ^ (I ^ K) (This adds up high)
pay_out = round((AA * BB ^ (I ^ K)),1) (but correctly sets hi and lo bounds)
.
. (more code to write out data)
.
end

Thanks in advance for any assistance
Bob
Hi Bob! Welcome to MHB!

I haven't tried to analyze your formulas, since I do not know what the rationale behind them is.
But am I right to assume the total amount paid out is almost the same as the payout pool?
If so, your problem is likely caused by rounding errors.

Simplest solution would be to reduce the payout pool by the difference and redo the calculation.

btaylor

New member
Thank you for the reply.

Yes on the total payout must match the amount in the payout pool.

Depending on the amount of the total pool, the difference in the total of all the calculated payoff /place can be thousands off unless I start messing with "K." I can get it pretty close but then the slope gets very steep from 1st to 2nd.

When I figure out how to attach some images to my posts, I'll get some screen shots of the setup and results window.

Bob

btaylor

New member
Hi Bob! Welcome to MHB!

I haven't tried to analyze your formulas, since I do not know what the rationale behind them is.
But am I right to assume the total amount paid out is almost the same as the payout pool?
If so, your problem is likely caused by rounding errors.

Simplest solution would be to reduce the payout pool by the difference and redo the calculation.
I am attaching two images one from a default setting after importing the total entry$. The other is a balanced payout but had to mess with the smoothing too much. Despite what the smoothing (K) is set at the total payout should always be in balance just with a tighter or bigger spread of payouts below 1st place. Simplest solution would be to reduce the payout pool by the difference and redo the calculation. Not possible. The upper and lower payouts and 80% (in this case) are guaranteed. Also, don't forget that all the fields on the left are variables and the user can modify them to what works best for his result. I don't have to stick with my original code (from the early 90's on Compuserve). If someone comes up with a better solution I'll sure code it to see if it works. Bob Attachments • 15.1 KB Views: 24 • 15.7 KB Views: 25 Klaas van Aarsen MHB Seeker Staff member Thank you for the reply. Yes on the total payout must match the amount in the payout pool. Depending on the amount of the total pool, the difference in the total of all the calculated payoff /place can be thousands off unless I start messing with "K." I can get it pretty close but then the slope gets very steep from 1st to 2nd. When I figure out how to attach some images to my posts, I'll get some screen shots of the setup and results window. Bob If there is too little money in the pool, there is no solution. And if there is just enough money, you will indeed get a steep slope... Klaas van Aarsen MHB Seeker Staff member I am attaching two images one from a default setting after importing the total entry$. The other is a balanced payout but had to mess with the smoothing too much. Despite what the smoothing (K) is set at the total payout should always be in balance just with a tighter or bigger spread of payouts below 1st place.

Simplest solution would be to reduce the payout pool by the difference and redo the calculation.

Not possible. The upper and lower payouts and 80% (in this case) are guaranteed. Also, don't forget that all the fields on the left are variables and the user can modify them to what works best for his result.

I don't have to stick with my original code (from the early 90's on Compuserve). If someone comes up with a better solution I'll sure code it to see if it works.

Bob
All right, I have just implemented a formula and an algorithm of my own.
I get:
Code:
Place   Calculated
1       100.00
2       100.00
3       100.00
4       100.06
5       100.51
6       102.65
7       110.20
8       131.87
9       185.52
10      304.23
11      544.95
12      1000.00
Total   2880.00
Or alternatively, when optimizing for rounded values:
Code:
Place   Calculated
1       100.00
2       100.00
3       100.00
4       100.00
5       101.00
6       103.00
7       110.00
8       132.00
9       185.00
10      304.00
11      545.00
12      1000.00
Total   2880.00
Would you consider either of them a better solution?

btaylor

New member
"If there is too little money in the pool, there is no solution.
And if there is just enough money, you will indeed get a steep slope..."

Then it is up the the director to adjust how many places he will pay and what the top and bottom amounts are.

The number of participants varies per event, the total pool will vary depending how much money is collected, thus dictating how many places and how much he wants to pay. One time he may have 20 and another time 200. On the 20 he may only pay 3 places; on 200 he may pay 30, 40, or 50 places. That's why they can muck around with the figures to get the best payout spread.

I would like to see what you developed. Can the variables be modified to allow for a flatter curve?

BTW, I may have mislead everybody on the needs. As noted on the screen shots, those  amounts are the minimums for that place payout. So if the top amount is > 1000 then that would be OK. Same with the minimum last payout.

I really appreciate your time at looking at this.

Bob

Klaas van Aarsen

MHB Seeker
Staff member
Well, here is the algorithm I used (bisection with a constant "power" curve).
I'm afraid it's in a different language than what you may be used to (C++).

Code:
#include <stdio.h>
#include <math.h>

double calcPrice(int place, int n, double m, double M, double power)
{
return m + (M - m) * pow((double)place / (n - 1), power);
}

void calcPayout(double payout, double m, double M, int n)
{
printf("Payout\t%.2f\n", payout);
printf("Max\t%.2f\n", M);
printf("Min\t%.2f\n", m);
printf("Places\t%.d\n", n);

int NMAX = 200;
double PAYOUT_TOL = 0.005;
double ALGORITHM_TOL = 0.00001;

bool solutionFound = false;
double a = 0.01;
double b = 100.0;
double c;
double fa = -1;
double fb = +1;
double fc;
for (int N = 1; N <= NMAX; ++N)
{
c = (a + b) / 2;

double sum = 0;
for (int i = 0; i < n; ++i)
{
sum = sum + calcPrice(i, n, m, M, c);
}
fc = payout - sum;
printf("%d\t%f\t%.2f\t%f\n", N, c, fc, (b - a) / 2);

if ((fabs(fc) < PAYOUT_TOL) || ((b - a) / 2 < ALGORITHM_TOL))
{
solutionFound = true;
break;
}

if (fc * fa >= 0)
{
a = c; fa = fc;
}
else
{
b = c; fb = fc;
}
}

if (!solutionFound)
{
printf("Bad solution\n");
}
else
{
printf("Place\tCalculated\n");
double sum = 0;
for (int i = 0; i < n; ++i)
{
double price = calcPrice(i, n, m, M, c);
sum = sum + price;
printf("%d\t%.2f\n", i + 1, price);
}
printf("Total\t%.2f\n\n", sum);
}
}

void main(void)
{
calcPayout(2880, 100, 1000, 12);
calcPayout(2880, 100, 1000, 12);
}
To introduce a parameter that influences the curve, you can use:

Code:
double gParameter = 0.0;

double calcPrice(int place, int n, double m, double M, double power)
{
double parameterToPower = pow(gParameter , power);
double lastPlaceToPower = pow(n - 1 + gParameter , power);

double factor = (M - m) / (lastPlaceToPower - parameterToPower);
double offset = m - factor * parameterToPower;
return offset + factor * pow((double)place + gParameter , power);
}

void calcPayout(double payout, double m, double M, int n)
{
...
}

void main(void)
{
calcPayout(2880, 100, 1000, 12);
gParameter = 1.0;
calcPayout(2880, 100, 1000, 12);
}
The parameter will have to be greater or equal to zero.

btaylor

New member
Thank you for the coding. I can handle C++ so I'll translate it and put into procedure to test.

It may be a while but I'll get some feedback to you.

Bob


text:
# Search by Topic

#### Resources tagged with Working systematically similar to Zooming in on the Squares:

Filter by: Content type:
Stage:
Challenge level:

### There are 338 results

Broad Topics > Using, Applying and Reasoning about Mathematics > Working systematically

### Tetrahedra Tester

##### Stage: 3 Challenge Level:

An irregular tetrahedron is composed of four different triangles. Can such a tetrahedron be constructed where the side lengths are 4, 5, 6, 7, 8 and 9 units of length?

### You Owe Me Five Farthings, Say the Bells of St Martin's

##### Stage: 3 Challenge Level:

Use the interactivity to listen to the bells ringing a pattern. Now it's your turn! Play one of the bells yourself. How do you know when it is your turn to ring?

### When Will You Pay Me? Say the Bells of Old Bailey

##### Stage: 3 Challenge Level:

Use the interactivity to play two of the bells in a pattern. How do you know when it is your turn to ring, and how do you know which bell to ring?

### Isosceles Triangles

##### Stage: 3 Challenge Level:

Draw some isosceles triangles with an area of $9$cm$^2$ and a vertex at (20,20). If all the vertices must have whole number coordinates, how many is it possible to draw?

### 9 Weights

##### Stage: 3 Challenge Level:

You have been given nine weights, one of which is slightly heavier than the rest. Can you work out which weight is heavier in just two weighings of the balance?

### Triangles to Tetrahedra

##### Stage: 3 Challenge Level:

Starting with four different triangles, imagine you have an unlimited number of each type. How many different tetrahedra can you make? Convince us you have found them all.

### More Magic Potting Sheds

##### Stage: 3 Challenge Level:

The number of plants in Mr McGregor's magic potting shed increases overnight. He'd like to put the same number of plants in each of his gardens, planting one garden each day. How can he do it?

### Making Squares

##### Stage: 2 Challenge Level:

Investigate all the different squares you can make on this 5 by 5 grid by making your starting side go from the bottom left hand point. Can you find out the areas of all these squares?

### Geoboards

##### Stage: 2 Challenge Level:

This practical challenge invites you to investigate the different squares you can make on a square geoboard or pegboard.

### My New Patio

##### Stage: 2 Challenge Level:

What is the smallest number of tiles needed to tile this patio? Can you investigate patios of different sizes?

### Tiles on a Patio

##### Stage: 2 Challenge Level:

How many ways can you find of tiling the square patio, using square tiles of different sizes?

### Fence It

##### Stage: 3 Challenge Level:

If you have only 40 metres of fencing available, what is the maximum area of land you can fence off?

### Squares in Rectangles

##### Stage: 3 Challenge Level:

A 2 by 3 rectangle contains 8 squares and a 3 by 4 rectangle contains 20 squares. What size rectangle(s) contain(s) exactly 100 squares? Can you find them all?

### Games Related to Nim

##### Stage: 1, 2, 3 and 4

This article for teachers describes several games, found on the site, all of which have a related structure that can be used to develop the skills of strategic planning.

### More Transformations on a Pegboard

##### Stage: 2 Challenge Level:

Use the interactivity to find all the different right-angled triangles you can make by just moving one corner of the starting triangle.

### Making Boxes

##### Stage: 2 Challenge Level:

Cut differently-sized square corners from a square piece of paper to make boxes without lids. Do they all have the same volume?

### Oranges and Lemons, Say the Bells of St Clement's

##### Stage: 3 Challenge Level:

Bellringers have a special way to write down the patterns they ring. Learn about these patterns and draw some of your own.

### Product Sudoku 2

##### Stage: 3 and 4 Challenge Level:

Given the products of diagonally opposite cells - can you complete this Sudoku?

### Uncanny Triangles

##### Stage: 2 Challenge Level:

Can you help the children find the two triangles which have the lengths of two sides numerically equal to their areas?

### Calcunos

##### Stage: 2 Challenge Level:

If we had 16 light bars which digital numbers could we make? How will you know you've found them all?

### Ratio Sudoku 3

##### Stage: 3 and 4 Challenge Level:

A Sudoku with clues as ratios or fractions.

### Diagonal Sums Sudoku

##### Stage: 2, 3 and 4 Challenge Level:

Solve this Sudoku puzzle whose clues are in the form of sums of the numbers which should appear in diagonal opposite cells.

### First Connect Three

##### Stage: 2 and 3 Challenge Level:

The idea of this game is to add or subtract the two numbers on the dice and cover the result on the grid, trying to get a line of three. Are there some numbers that are good to aim for?

### Three Sets of Cubes, Two Surfaces

##### Stage: 2 Challenge Level:

How many models can you find which obey these rules?

### Magic Potting Sheds

##### Stage: 3 Challenge Level:

Mr McGregor has a magic potting shed. Overnight, the number of plants in it doubles. He'd like to put the same number of plants in each of three gardens, planting one garden each day. Can he do it?

### Maths Trails

##### Stage: 2 and 3

The NRICH team are always looking for new ways to engage teachers and pupils in problem solving. Here we explain the thinking behind maths trails.

### Broken Toaster

##### Stage: 2 Short Challenge Level:

Only one side of a two-slice toaster is working. What is the quickest way to toast both sides of three slices of bread?

### Twinkle Twinkle

##### Stage: 2 and 3 Challenge Level:

A game for 2 people. Take turns placing a counter on the star. You win when you have completed a line of 3 in your colour.

### Intersection Sudoku 1

##### Stage: 3 and 4 Challenge Level:

A Sudoku with a twist.

### Sticky Numbers

##### Stage: 3 Challenge Level:

Can you arrange the numbers 1 to 17 in a row so that each adjacent pair adds up to a square number?

### Twin Corresponding Sudoku III

##### Stage: 3 and 4 Challenge Level:

Two sudokus in one. Challenge yourself to make the necessary connections.

### Ratio Sudoku 2

##### Stage: 3 and 4 Challenge Level:

A Sudoku with clues as ratios.

### Ice Cream

##### Stage: 2 Challenge Level:

You cannot choose a selection of ice cream flavours that includes totally what someone has already chosen. Have a go and find all the different ways in which seven children can have ice cream.

### Intersection Sudoku 2

##### Stage: 3 and 4 Challenge Level:

A Sudoku with a twist.

### Button-up Some More

##### Stage: 2 Challenge Level:

How many ways can you find to do up all four buttons on my coat? How about if I had five buttons? Six ...?

### Seasonal Twin Sudokus

##### Stage: 3 and 4 Challenge Level:

This pair of linked Sudokus matches letters with numbers and hides a seasonal greeting. Can you find it?

### Area and Perimeter

##### Stage: 2 Challenge Level:

What can you say about these shapes? This problem challenges you to create shapes with different areas and perimeters.

### LOGO Challenge - the Logic of LOGO

##### Stage: 3 and 4 Challenge Level:

Just four procedures were used to produce a design. How was it done? Can you be systematic and elegant so that someone can follow your logic?

### Newspapers

##### Stage: 2 Challenge Level:

When newspaper pages get separated at home we have to try to sort them out and get things in the correct order. How many ways can we arrange these pages so that the numbering may be different?

##### Stage: 3 Challenge Level:

How many different symmetrical shapes can you make by shading triangles or squares?

### Numerically Equal

##### Stage: 2 Challenge Level:

Can you draw a square in which the perimeter is numerically equal to the area?

### Instant Insanity

##### Stage: 3, 4 and 5 Challenge Level:

Given the nets of 4 cubes with the faces coloured in 4 colours, build a tower so that on each vertical wall no colour is repeated, that is all 4 colours appear.

### Sums and Differences 2

##### Stage: 2 Challenge Level:

Find the sum and difference between a pair of two-digit numbers. Now find the sum and difference between the sum and difference! What happens?

### Square Corners

##### Stage: 2 Challenge Level:

What is the greatest number of counters you can place on the grid below without four of them lying at the corners of a square?

### Cover the Tray

##### Stage: 2 Challenge Level:

These practical challenges are all about making a 'tray' and covering it with paper.

### Halloween Investigation

##### Stage: 2 Challenge Level:

Ana and Ross looked in a trunk in the attic. They found old cloaks and gowns, hats and masks. How many possible costumes could they make?

### Sums and Differences 1

##### Stage: 2 Challenge Level:

This challenge focuses on finding the sum and difference of pairs of two-digit numbers.

### Consecutive Negative Numbers

##### Stage: 3 Challenge Level:

Do you notice anything about the solutions when you add and/or subtract consecutive negative numbers?

format: plain


text:
# 5.5: Permutations and Combinations

• Page ID
2108
• Skills to Develop

• Calculate the probability of two independent events occurring
• Define permutations and combinations
• List all permutations and combinations
• Apply formulas for permutations and combinations

This section covers basic formulas for determining the number of various possible types of outcomes. The topics covered are:

• counting the number of possible orders
• counting using the multiplication rule
• counting the number of permutations
• counting the number of combinations

### Possible Orders

Suppose you had a plate with three pieces of candy on it: one green, one yellow, and one red. You are going to pick up these three pieces one at a time. The question is: In how many different orders can you pick up the pieces? Table $$\PageIndex{1}$$ lists all the possible orders.

Figure $$\PageIndex{1}$$: Candy

There are two orders in which red is first: red, yellow, green and red, green, yellow. Similarly, there are two orders in which yellow is first and two orders in which green is first. This makes six possible orders in which the pieces can be picked up.

Table $$\PageIndex{1}$$: Six Possible Orders.
Number First Second Third
1 red yellow green
2 red green yellow
3 yellow red green
4 yellow green red
5 green red yellow
6 green yellow red

The formula for the number of orders is shown below.

$\text{Number of orders} = n!$

where $$n$$ is the number of pieces to be picked up. The symbol "!" stands for factorial. Some examples are:

\begin{align} 3! &= 3 \times 2 \times 1 = 6 \\ 4! &= 4 \times 3 \times 2 \times 1 = 24 \\ 5! &= 5 \times 4 \times 3 \times 2 \times 1 = 120 \end{align}

This means that if there were $$5$$ pieces of candy to be picked up, they could be picked up in any of $$5! = 120$$ orders.

### Multiplication Rule

Imagine a small restaurant whose menu has $$3$$ soups, $$6$$ entrées, and $$4$$ desserts. How many possible meals are there? The answer is calculated by multiplying the numbers to get $$3 \times 6 \times 4 = 72$$. You can think of it as first there is a choice among $$3$$ soups. Then, for each of these choices there is a choice among $$6$$ entrées resulting in $$3 \times 6 = 18$$ possibilities. Then, for each of these $$18$$ possibilities there are $$4$$ possible desserts yielding $$18 \times 4 = 72$$ total possibilities.

### Permutations

Suppose that there were four pieces of candy (red, yellow, green, and brown) and you were only going to pick up exactly two pieces. How many ways are there of picking up two pieces? Table $$\PageIndex{2}$$ lists all the possibilities. The first choice can be any of the four colors. For each of these $$4$$ first choices there are $$3$$ second choices. Therefore there are $$4 \times 3 = 12$$ possibilities.

Table $$\PageIndex{2}$$: Twelve Possible Orders
Number First Second
1 red yellow
2 red green
3 red brown
4 yellow red
5 yellow green
6 yellow brown
7 green red
8 green yellow
9 green brown
10 brown red
11 brown yellow
12 brown green

More formally, this question is asking for the number of permutations of four things taken two at a time. The general formula is:

$_nP_r = \dfrac{n!}{(n-r)!}$

where $$_nP_r$$ is the number of permutations of $$n$$ things taken $$r$$ at a time. In other words, it is the number of ways $$r$$ things can be selected from a group of $$n$$ things. In this case,

$_4P_2 = \dfrac{4!}{(4-2)!} = \dfrac{4 \times 3 \times 3 \times 2 \times 1}{2 \times 1} = 12$

It is important to note that order counts in permutations. That is, choosing red and then yellow is counted separately from choosing yellow and then red. Therefore permutations refer to the number of ways of choosing rather than the number of possible outcomes. When order of choice is not considered, the formula for combinations is used.

### Combinations

Now suppose that you were not concerned with the way the pieces of candy were chosen but only in the final choices. In other words, how many different combinations of two pieces could you end up with? In counting combinations, choosing red and then yellow is the same as choosing yellow and then red because in both cases you end up with one red piece and one yellow piece. Unlike permutations, order does not count. Table $$\PageIndex{3}$$ is based on Table $$\PageIndex{2}$$ but is modified so that repeated combinations are given an "$$x$$" instead of a number. For example, "yellow then red" has an "$$x$$" because the combination of red and yellow was already included as choice number $$1$$. As you can see, there are six combinations of the three colors.

Table $$\PageIndex{1}$$: Six Combinations.
Number First Second
1 red yellow
2 red green
3 red brown
x yellow red
4 yellow green
5 yellow brown
x green red
x green yellow
6 green brown
x brown red
x brown yellow
x brown green

The formula for the number of combinations is shown below where $$_nC_r$$ is the number of combinations for $$n$$ things taken $$r$$ at a time.

$_nC_r = \dfrac{n!}{(n-r)!r!}$

For our example,

$_4C_2 = \dfrac{4!}{(4-2)!2!} = \dfrac{4 \times 3 \times 3 \times 2 \times 1}{(2 \times 1)(2 \times 1)} = 6$

which is consistent with Table $$\PageIndex{3}$$.

As an example application, suppose there were six kinds of toppings that one could order for a pizza. How many combinations of exactly $$3$$ toppings could be ordered? Here $$n = 6$$ since there are $$6$$ toppings and $$r = 3$$ since we are taking $$3$$ at a time. The formula is then:

$_6C_3 = \dfrac{6!}{(6-3)!3!} = \dfrac{6\times 5 \times 4 \times 3 \times 3 \times 2 \times 1}{(3 \times 2 \times 1)(3 \times 2 \times 1)} = 30$

### Contributor

• Online Statistics Education: A Multimedia Course of Study (http://onlinestatbook.com/). Project Leader: David M. Lane, Rice University.


text:
## Tuesday, April 1, 2014

### Melbourne's Weather and Cross Correlations

During a lunchtime discussion among recent GCaP class attendees, the topic of weather came up and I casually mentioned that the weather in Melbourne, Australia, can be very changeable because the continent is so old that there is very little geographical relief to moderate the prevailing winds coming from the west.

In general, Melbourne is said to have a mediterranean climate, but it can also be subject to cold blasts of air coming up from Antarctic regions at any time, but especially during the winter. Fortunately, the island state of Tasmania acts as something of a geographical barrier against those winds. Understanding possible relationships between these effects presents an interesting exercise in correlation analysis.

### Gathering Weather Data

Weather data for all major Australia cities are available from the Bureau of Meteorology. The subsequent discussion will employ weather records for the past calendar year (2013) collected from Perth, in Western Australia, and Hobart and Launceston, in Tasmania. The city of Perth has been in the news lately because it's the base for aircraft searching for wreckage of Malaysian Airlines flight MH 370. The available weather indicators include daily min and max temperatures and rainfall.

Figure 1 shows maximum temperatures in degrees Celsius. The trough occurs in the middle of the calendar year because that's the winter season in Australia.

Which city is most strongly correlated with Melbourne's temperatures? It's impossible to decide based on the raw data alone. To answer such questions more rigorously we can use the cross correlation function (CCF) in R.

### Cross Correlation Plots

Applying the ccf function to the data in Fig. 1:

mel.ts  <- ts(df.mel$MaxT) per.ts <- ts(df.per$MaxT)
hob.ts  <- ts(df.hob$MaxT) laun.ts <- ts(df.laun$MaxT)

ccf(per.ts,mel.ts)
ccf(hob.ts,mel.ts)
ccf(laun.ts,mel.ts)

produces the plots shown in Fig. 2.

Like a ripple in a pond, there can be a delay or lag between an event exhibiting itself in one time series and it's effect showing up in the other time series. So, simply calculating the correlation coefficient at the same point in time for both series is not sufficient.

The CCF is defined as the set of correlations (height of the vertical line segments in Fig. 2) between two time series $x_t + h$ and $y_t$ for lags $h = 0, \pm1, \pm2, \ldots$. A negative value for $h$ represents a correlation between the x-series at a time before $t$ and the y-series at time $t$. If, for example, the lag $h = -3$, then the cross correlation value would give the correlation between $x_t - 3$ and $y_t$. Negative line segments correspond to events that are anti-correlated.

The CCF helps to identify lags of $x_t$ that could be predictors of the $y_t$ series.

1. When $h < 0$ (left side of plots in Fig. 2), $x$ leads $y$.
2. When $h > 0$ (right side of plots in Fig. 2), $x$ lags $y$.
For the weather correlation analysis, we would like to identify which series is leading or influencing the Melbourne time series.

### Interpreting the CCF Plots

The dominant or fundamental signal over 365 days in Fig. 1 resembles one period of a sine wave. The first row in Fig. 3. shows two pure sine waves (red and blue) that are in phase with each other (left column). The correlation plot (right column ) shows a peak at $h=0$, in the middle of the plot, indicating that the two curves are most strongly correlated when there is no horizontal displacement between the curves.

The second row in Fig. 3. shows sine waves that are 90 degrees out of phase with each other (left column ). The correlation plot (right column ) shows that these two curves are most weakly correlated at zero lag. Conversely, they are more strongly correlated at $h=-16$ (left side of CCF plot) or anti-correlated at $h=+16$ (right side of CCF plot).

The third row in Fig. 3 is similar to the first row but with some Gaussian noise added to both signals. The correlation plot shows a slight loss of symmetry but otherwise doesn't indicate much additional structure because the randomness of the noise in both signals tends to cancel out.

Figure 4 has the same signals as Fig. 3 but with 365 sample points to match the weather data in Fig. 1. This has the effect of broadening out the correlation plots and, indeed, they do more closely resemble the correlation plots in Fig. 2.

# Perth-Melbourne analysis
ccf(per.ts,mel.ts,plot=FALSE)
# produces the numerical output:

Autocorrelations of series ‘X’, by lag

-22   -21   -20   -19   -18   -17   -16   -15   -14   -13   -12   -11   -10    -9    -8    -7    -6
0.542 0.498 0.488 0.511 0.525 0.545 0.563 0.550 0.549 0.554 0.588 0.576 0.599 0.594 0.549 0.540 0.615
-5    -4    -3    -2    -1     0     1     2     3     4     5     6     7     8     9    10    11
0.631 0.617 0.656 0.595 0.508 0.475 0.512 0.559 0.605 0.618 0.555 0.500 0.512 0.543 0.548 0.536 0.533
12    13    14    15    16    17    18    19    20    21    22
0.525 0.504 0.523 0.520 0.489 0.478 0.494 0.501 0.484 0.503 0.519

pm <- ccf(per.ts,mel.ts)
max.pmc <- max(pm$acf) # produces the output:[1] 0.6564855 # At what lag? pm$lag[which(pm$acf > max.pmc-0.01 & pm$acf < max.pmc+0.01)]
# produces the output: [1] -3

We can carry out the same analysis for Hobart-Melbourne time series:

# Hobart-Melbourne analysis
hm <- ccf(hob.ts,mel.ts)
max.hmc <- max(hm$acf) pm$lag[which(hm$acf > max.hmc-0.01 & hm$acf < max.hmc+0.01)]
# 0.8269252 occurs at lag h = 0

and Launceston-Melbourne time series:

# Launceston-Melbourne analysis
lm <- ccf(laun.ts,mel.ts)
max.lmc <- max(lm$acf) lm$lag[which(lm$acf > max.lmc-0.01 & lm$acf < max.lmc+0.10)]
# Two lags satisfy this criterion
# 0.801 occurs at lag h = 0
# 0.791 occurs at lag h = -1

Next, we need to interpret all these statistics.

### Analysis and Conclusions

It does indeed take about three days for weather to cross the 2000 miles between Perth and Melbourne. But the correlation at lag $h = -3$ is only 0.66, whereas it's closer to 0.80 for Hobart and Launceston. To help interpret these correlation values we note that the GIS coordinates of the respective cities are:

The prevailing westerly winds originate with the Roaring Forties in the Indian Ocean. That name is a reference to 40 degrees south latitude. Melbourne is located at about 38 degrees south latitude. Perth, on the other hand, is located at a latitude much further north; it's even north of Sydney! In addition, there is a considerable desert region (roughly two thirds of the breadth of the continent) between Perth and Melbourne. Therefore, we can expect the correlations between Perth and Melbourne temperatures to be weaker than those associated with the Tasmanian cities.

Hobart is further south than Melbourne and, although it's on the eastern side of the Tasmanian island, there is no other land mass between the longitudes at Perth and Hobart. Hence, Hobart and Melbourne are more strongly correlated than Perth at zero lag.

Launceston is closest to Melbourne by latitude and, at zero lag, has a similar correlation to that for Hobart. No surprise there. There is one difference, however. A similar correlation exists at $h = -1$, which means Launceston leads Melbourne by a day, even though it is slightly east of Melbourne by about two degrees longitude. How can that be? One possibility is that it represents the effect of more southerly winds, such as those originating with the Screaming Sixties, circulating approximately counter-clockwise around the east coast of Tasmania. Cross correlated cross winds.

I'll cover more about time series analysis in the upcoming Guerrilla Data Analysis Techniques class.

These are the same winds used by the early European traders, like the Dutch and Portugese, to reach the "spice islands" in the Indonesian archipelago. Hence the term trade winds. The basic idea was, you sail down the west coast of Africa, round the Cape of Good Hope, catch the Roaring Forties across the Indian Ocean, and hang a left at about 100 degrees east longitude. All this was at a time before longitude could be determined accurately. In 1616, the Dutch naval explorer, Dirk Hartog, missed that off-ramp and found himself staring at the west coast of Australia. Hence, the name of the continent was changed from Terra Australis (Southern Land) to Neu Holland (New Holland) on maps of the day. In a similar way, another Dutch navigator, Abel Tasman, sighted the west coast of Tasmania and named it Van Diemen's Land. Two centuries later, it was renamed after Tasman.

## Thursday, March 13, 2014

### Performance of N+1 Redundancy

How can you determine the performance impact on SLAs after an N+1 redundant hosting configuration fails over? This question came up in the Guerrilla Capacity Planning class, this week. It can be addressed by referring to a multi-server queueing model.

### N+1 = 4 Redundancy

We begin by considering a small-N configuration of four hosts where the load is distributed equally to each of the hosts. For simplicity, the load distribution is assumed to be performed by some kind of load balancer with a buffer. The idea of N+1 redundancy is that the load balancer ensures all four hosts are utilized. The common misconception is that none of the hosts should consume more than 75% of their available capacity. Referring to Fig. 1, the total consumed capacity is assumed to be $4 \times 3/4 = 3$ or 300% of the configuration (rather than 400%) so that, when one of the hosts fails, its lost capacity is compensated by redistributing that load across the remaining three available hosts.

The circles in Fig. 1 represent hosts and rectangles represent incoming requests buffered at the load-balancer. The blue area in the circles signifies the available capacity of a host, whereas white signifies unavailable capacity. When one of the hosts fails, its load must be redistributed across the remaining three hosts. What Fig. 1 doesn't show is the performance impact of this capacity redistribution.

### N+1 = 4 Performance

The performance metric of interest is response time as it pertains to service targets expressed in SLAs. To assess the performance impact of failover, we model the N+1 configuration as an M/M/4 queue with per-server utilization constrained to be no more than 75% busy.

When a failover event occurs, the configuration becomes an M/M/3 queue. The corresponding response time curves are shown in Fig. 2. The y-axis is the response time, R, expressed as multiples of the service period, S. A typical scenario is where the SLA (horizontal line) corresponds to maximum or near maximum utilization. The SLA in this case is a mean response time no greater than 1.45 service periods.

On failover, upon which only three hosts remain available, the SLA will be exceeded because the utilization of each host will be heading for 100% due to the additional load. (See Fig. 1) Correspondingly, this has the effect of pushing the response time very high up the M/M/3 curve. In order to maintain the SLA, the load would have to be reduced so that it corresponds to a lower utilization of 68.25%. Fig. 3 shows this effect in more detail.

In practice, proper capacity planning, such as the M/M/m queueing models employed in this discussion, would have revealed that the maximum host utilization should not have exceeded 68.25% busy in the N+1 configuration.

### Large-N Performance

With a large number of hosts the difference in response time after failover becomes less significant. This follows from the fact that response-time curves for an M/M/m queue are flatter at high utilizations when the number of servers, m, is large. The effect is illustrated in Fig. 4 for N+1 = 16 hosts. (cf. Fig. 2)

However, the most common installations are small-N configurations of the type discussed in the previous section. Therefore, preserving your SLA requires capacity planning based on host utilizations that match your SLA targets.

Thanks to the GCaP class participants for doing a group-edit on this post in real time.

## Wednesday, March 12, 2014

### Modeling the Mythical Man-Month

This article was originally posted in 2007. When I updated the image today (in 2014), it reappeared with the more recent date and I don't know how to override that (wrong) timestamp. This seems to be a bug in Blogger.

In the aftermath of a discussion about software management with my colleague Steve Jenkin, I looked up the Mythical Man-Month concept in wikipedia. The main thesis of Fred Brooks, often referred to as "Brooks's law [sic]," is simply stated as:

Adding manpower to a late software project makes it later.
In other words, some number of cooks are necessary to prepare a dinner, but adding too many cooks in the kitchen can inflate the delivery schedule.

## Wednesday, February 19, 2014

### Facebook Meets Florence Nightingale and Enrico Fermi

Highlighting Facebook's mistakes and weaknesses is a popular sport. When you're the 800 lb gorilla of social networking, it's inevitable. The most recent rendition of FB bashing appeared in a serious study entitled, Epidemiological Modeling of Online Social Network Dynamics, authored by a couple of academics in the Department of Mechanical and Aerospace Engineering (???) at Princeton University.

They use epidemiological models to explain adoption and abandonment of social networks, where user adoption is analogous to infection and user abandonment is analogous to recovery from disease, e.g., the precipitous attrition witnessed by MySpace. To this end, they employ variants of an SIR (Susceptible Infected Removed) model to predict a precipitous decline in Facebook activity in the next few years.

Channeling Mark Twain, FB engineers lampooned this conclusion by pointing out that Princeton would suffer a similar demise under the same assumptions.

Irrespective of the merits of the Princeton paper, I was impressed that they used an SIR model. It's the same one I used, in R, last year to reinterpret Florence Nightingale's zymotic disease data during the Crimean War as resulting from epidemic spreading.

Another way in which FB was inadvertently dinged by incorrect interpretation of information—this time it was the math—occurred in the 2010 movie, "The Social Network" that tells the story of how FB (then called Facemash) came into being. While watching the movie, I noticed that the ranking metric that gets written on a dorm window (only in Hollywood) is wrong! The correct ranking formula is analogous to the Fermi-Dirac distribution, which is key to understanding how electrons "rank" themselves in atoms and semiconductors.

"The reports of my death have been greatly exaggerated."

## Tuesday, February 18, 2014

### Guerrilla Classes in March 2014

The upcoming GBoot and GCaP training classes are your fast track to enterprise performance and capacity management. You can now register entirely online using either your corporate or personal credit card.

New topics include:

• The effect of think-time settings in load tests

Classic topics include:

• There are only 3 performance metrics
• How performance metrics are related to each another
• How to quantify scalability with the Universal Scalability Law (USL)
• IT Infrastructure Library (ITIL) for Guerrillas
• The Virtualization Spectrum from hyperthreads to hyperservices

As usual, all classes are held at our lovely Larkspur Landing Pleasanton location in California. Attendees should bring their laptops to the class as course materials are provided on a flash drive. Larkspur Landing also provides free wi-fi Internet in their residence-style rooms as well as the training room.

## Thursday, January 2, 2014

### Monitoring CPU Utilization Under Hyper-threading

The question of accurately measuring processor utilization with hyper-threading (HT) enabled came up recently in a Performance Engineering Group discussion on Linked-in. Since I spent some considerable time looking into this issue while writing my Guerrilla Capacity Planning book, I thought I'd repeat my response here (slightly edited for this blog), in case it's useful to a broader audience interested in performance and capacity management. Not much has changed, it seems.

In a nutshell, the original question concerned whether or not it was possible for a single core to be observed running at 200% busy, as reported by Linux top, when HT is enabled.

This question is an old canard (well, "old" for multicore technology). I call it the "Missing MIPS" paradox. Regarding the question, "Is it really possible for a single core to be 200% busy?" the short answer is: never! So, you are quite right to be highly suspicious and confused.

You don't say which make of processor is running on your hardware platform, but I'll guess Intel. Very briefly, the OS (Linux in your case) is being lied to. Each core has 2 registers where inbound threads are stored for processing. Intel calls these AS (Architectural State) registers. With HT *disabled*, the OS only sees a single AS register as being available. In that case, the mapping between state registers and cores is 1:1. The idea behind HT is to allow a different application thread to run when the currently running app stalls; due to branch misprediction, bubbles in the pipeline, etc. To make that possible, there has to be another port or AS register. That register becomes visible to the OS when HT is enabled. However, the OS (and all the way up the food chain to whatever perf tools you are using) now thinks twice the processor capacity is available, i.e., 100% CPU at each AS port.

## Wednesday, December 25, 2013

### Response Time Percentiles for Multi-server Applications

In a previous post, I applied my rules-of-thumb for response time (RT) percentiles (or more accurately, residence time in queueing theory parlance), viz., 80th percentile: $R_{80}$, 90th percentile: $R_{90}$ and 95th percentile: $R_{95}$ to a cellphone application and found that the performance measurements were not completely consistent. Since the relevant data only appeared in a journal blog, I didn't have enough information to resolve the discrepancy; which is ok. The first job of the performance analyst is to flag performance anomalies but most probably let others resolve them—after all, I didn't build the system or collect the measurements.

More importantly, that analysis was for a single server application (viz., time-to-first-fix latency). At the end of my post, I hinted at adding percentiles to PDQ for multi-server applications. Here, I present the corresponding rules-of-thumb for the more ubiquitous multi-server or multi-core case.

### Single-server Percentiles

First, let's summarize the Guerrilla rules-of-thumb for single-server percentiles (M/M/1 in queueing parlance): \begin{align} R_{1,80} &\simeq \dfrac{5}{3} \, R_{1} \label{eqn:mm1r80}\\ R_{1,90} &\simeq \dfrac{7}{3} \, R_{1}\\ R_{1,95} &\simeq \dfrac{9}{3} \, R_{1} \label{eqn:mm1r95} \end{align} where $R_{1}$ is the statistical mean of the measured or calculated RT and $\simeq$ denotes approximately equal. A useful mnemonic device is to notice the numerical pattern for the fractions. All denominators are 3 and the numerators are successive odd numbers starting with 5.


text:
# How Were Sine, Cosine and Tangent Formulas Conceived? [closed]

I am looking mostly, for a visual answer since I am not so advanced in mathematics.

1. When solving for the opposite side, for example, how does the formula convert degrees to a measurement, say 2 inches?
2. I have read about certain "tables" being used to aid these formulas. Why do we need these tables?
3. Why is it so complex to find the length of a side of a triangle?

My ideal answer is one that explains the why of the complexity of these formulas as they were being developed.

P.S. To answer below comment, by "complex" I meant that coming up with the formula for sine, cosine etc is no trivial task. So... I would like to know why it's not so simple to create said formulas, in a visual manner if possible.

## closed as unclear what you're asking by Hans Lundmark, John B, vonbrand, Chris Godsil, user147263 Feb 29 '16 at 2:25

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

• Related: History of sine function – Dave L. Renfro Feb 26 '16 at 22:20
• For #1, we need to be more specific about "the formula". No trig function actually converts degrees to inches, so you need something else that has "inches". For #3, what's "complex"? The definitions of the functions are incredibly simple and they have many very simple properties. Just how much simpler did you expect them to be? It would help if you were gave much more specific and complete examples for each part of the question; as it is, it seems to me this question is verging on "too broad for MSE", since we have to guess too much about what particular things are causing you confusion. – David K Feb 26 '16 at 22:24
• @DavidK: Re #1: Perhaps OP is looking to understand how a function takes an angular measure and converts it into a linear measure. – Brian Tung Feb 26 '16 at 23:36
• @BrianTung But the trig functions don't do that; they take angular measures and convert them to ratios of linear measures. You can't find the length of the opposite side just from the sine of an angle; you also need the length of the hypotenuse, which is where the "inches" (if any) will come from. – David K Feb 26 '16 at 23:39
• @DavidK: Quite right, I was sloppy. It turns it into a dimensionless measure. (Nonetheless, part of what I was trying to convey—that the result is some indication of length, even as a ratio—may be puzzling the OP.) – Brian Tung Feb 26 '16 at 23:46

The origins of these functions lies in two theorems of plane geometry that the Greeks discovered long ago:

• The sum of the angles of a triangle add up to $180^\circ$. (For the Greeks, this was "two right angles", but I'm translating into more modern terminology.)
• If two triangles have all three angles the same size as corresponding angles on the other triangle, then they are similar. That is, the ratios of corresponding sides are all the same.

So, suppose you have two right triangles. Then these two triangles each already have angles that are the same size, namely the right angle. Now suppose that they happen to have another angle with common measure. Because the sums of the three angles in each triangle add up to $180^\circ$, the third angles of each must also be the same size. Thus right triangles only need to have one other angle the same to be similar.

So ratios of corresponding sides of the two triangles above have to be the same: $$\frac aA = \frac bB = \frac cC$$

A little bit of algebra gives us $$\frac ac = \frac AC,\ \ \frac bc = \frac BC,\ \ \frac ba = \frac BA$$

Label the sides by their relation to the angle $\theta$:

We see that:

for any right triangle with one of its angles equal to $\theta$, no matter what size, the ratios of $\frac {\text{adjacent}}{\text{hypotenuse}}, \frac {\text{opposite}}{\text{hypotenuse}}, \frac {\text{opposite}}{\text{adjacent}}$ are the same as for all the other such right triangles.

Thus $\theta$ completely defines these three ratios. For this reason, we give them the special names cosine, sine, and tangent.

\begin{align}\cos \theta &= \frac {\text{adjacent}}{\text{hypotenuse}}\\ \sin \theta &= \frac {\text{opposite}}{\text{hypotenuse}}\\ \tan \theta &= \frac {\text{opposite}}{\text{adjacent}}\end{align}

(The name "tangent" comes from the fact that opposite side is tangent to a circle. The name "sine" originated as the name for "half-chord", but this was abbreviated by Arabic mathematicians, then some time later after the source of this abbreviation was forgotten, was expanded again to a word meaning "cave". That word was translated back to latin "sinus", and thus to "sine". "Cosine" comes from being complementary to sine.)

So, what is the point? Because sometimes (indeed, very commonly), you can't directly measure a distance that you want to know. See that tree outside? Want to know how tall it is? If it is a big tree, directly measuring its height is a very difficult proposition.

(Picture borrowed from http://www.monumentaltrees.com/en/content/measuringheight)

But if you can locate a point directly under it's tallest height, then measure the horizontal distance to some point far enough away to see the top. From that point, measure the angle your line of sight makes with the horizontal. This forms a right triangle, with the height of the tree as the opposite side, the distance you measured along the ground as the adjacent side, and the angle you measured as $\theta$. So go look up the tangent of your angle, and multiply:

$$\text{opposite} = \text{adjacent} \times \tan \theta$$

and now you know the height, without having to measure it directly. Of course, this is a simple example. In real life examples, the math is a little harder, but variants of this method allow you measure all sorts of distances where you can't get "directly under its highest point". The entire science of surveying is based on this.

So, knowing what the values of sine, cosine, and tangent are for various angles is a very, very useful thing. Now it is simple to get them. Just plug your angle into a calculator. But calculators are only about 40 years old and computers in general are less than 80 years old. Before then, mathematicians carefully worked out by hand the sine, cosine, and tangent of ranges of angles between $0^\circ$ and $90^\circ$, and listed these values in tables. To find the value for an angle not in the table, you found the nearest angles above and below, and linearly interpolated between them. Some of us who are older were taught to do that, because even though calculators existed then, they were not universal, and we were still taught the old techniques (I just missed having to learn to use a slide rule, myself.)


text:
$$\require{cancel}$$

# 19.3: Electrical Potential Due to a Point Charge

Point charges, such as electrons, are among the fundamental building blocks of matter. Furthermore, spherical charge distributions (like on a metal sphere) create external electric fields exactly like a point charge. The electric potential due to a point charge is, thus, a case we need to consider. Using calculus to find the work needed to move a test charge $$q$$ from a large distance away to a distance of $$r$$ from a point charge $$Q$$, and noting the connection between work and potential $$(W=-q\Delta V)$$, we can define the electric potential $$V$$ of a point charge:

definition: ELECTRIC POTENTIAL $$V$$ OF A POINT CHARGE

The electric potential $$V$$ of a point charge is given by

$V=\dfrac{kQ}{r}\: (\mathrm{Point\: Charge}). \label{eq1}$

where $$k$$ is a constant equal to $$9.0 \times 10^{9}\, \mathrm{N}\cdot \mathrm{m^{2}/C^{2}}.$$

The potential at infinity is chosen to be zero. Thus $$V$$ for a point charge decreases with distance, whereas $$\mathbf{E}$$ for a point charge decreases with distance squared:

$E=\dfrac{F}{q}=\dfrac{kQ}{r^{2}}.$

Recall that the electric potential $$V$$ is a scalar and has no direction, whereas the electric field $$\mathbf{E}$$ is a vector. To find the voltage due to a combination of point charges, you add the individual voltages as numbers. To find the total electric field, you must add the individual fields as vectors, taking magnitude and direction into account. This is consistent with the fact that $$V$$ is closely associated with energy, a scalar, whereas $$\mathbf{E}$$ is closely associated with force, a vector.

Example $$\PageIndex{1}$$: What Voltage Is Produced by a Small Charge on a Metal Sphere?

Charges in static electricity are typically in the nanocoulomb $$(\mathrm{nC})$$ to microcoulomb $$(\mu \mathrm{C})$$ range. What is the voltage 5.00 cm away from the center of a 1-cm diameter metal sphere that has a $$-3.00 \mathrm{nC}$$ static charge?

Strategy

As we have discussed in Electric Charge and Electric Field, charge on a metal sphere spreads out uniformly and produces a field like that of a point charge located at its center. Thus we can find the voltage using Equation \ref{eq1}.

Solution

Entering known values into the expression for the potential of a point charge, we obtain

\begin{align*} V&=k\dfrac{Q}{r} \\[5pt] &=(8.99 \times 10^{9} \, \mathrm{N}\cdot \mathrm{m^{2}/C^{2}}) \left(\dfrac{-3.00\times 10^{-9}\,\mathrm{C}}{5.00\times 10^{-2}\,\mathrm{m}}\right) \\[5pt] &= -539\, \mathrm{V}. \end{align*}

Discussion

The negative value for voltage means a positive charge would be attracted from a larger distance, since the potential is lower (more negative) than at larger distances. Conversely, a negative charge would be repelled, as expected.

Example $$\PageIndex{2}$$: What Is the Excess Charge on a Van de Graaff Generator

A demonstration Van de Graaff generator has a 25.0 cm diameter metal sphere that produces a voltage of 100 kV near its surface. (Figure $$\PageIndex{1}$$) What excess charge resides on the sphere? (Assume that each numerical value here is shown with three significant figures.)

Figure $$\PageIndex{1}$$: The voltage of this demonstration Van de Graaff generator is measured between the charged sphere and ground. Earth’s potential is taken to be zero as a reference. The potential of the charged conducting sphere is the same as that of an equal point charge at its center.

Strategy

The potential on the surface will be the same as that of a point charge at the center of the sphere, 12.5 cm away. (The radius of the sphere is 12.5 cm.) We can thus determine the excess charge using Equation \ref{eq1}.

Solution

Solving for $$Q$$ and entering known values gives

\begin{align*} Q &=\dfrac{rV}{k} \\[5pt] &= \dfrac{(0.125 \,\mathrm{m})(100\times 10^{3}\, \mathrm{V})}{8.99\times 10^{9}\, \mathrm{N\cdot m^{2}/C^{2}}} \\[5pt] &= 1.39\times 10^{-6} \,\mathrm{C} \\[5pt] &= 1.39\, \mathrm{\mu C}.\end{align*}

Discussion

This is a relatively small charge, but it produces a rather large voltage. We have another indication here that it is difficult to store isolated charges.

The voltages in both of these examples could be measured with a meter that compares the measured potential with ground potential. Ground potential is often taken to be zero (instead of taking the potential at infinity to be zero). It is the potential difference between two points that is of importance, and very often there is a tacit assumption that some reference point, such as Earth or a very distant point, is at zero potential. This is analogous to taking sea level as $$h=0$$ when considering gravitational potential energy, $$\mathrm{PE_{g}}=mgh$$.

### Summary

• Electric potential of a point charge is $$V=kQ/r$$.
• Electric potential is a scalar, and electric field is a vector. Addition of voltages as numbers gives the voltage due to a combination of point charges, whereas addition of individual fields as vectors gives the total electric field.

### Contributors

• Paul Peter Urone (Professor Emeritus at California State University, Sacramento) and Roger Hinrichs (State University of New York, College at Oswego) with Contributing Authors: Kim Dirks (University of Auckland) and Manjula Sharma (University of Sydney). This work is licensed by OpenStax University Physics under a Creative Commons Attribution License (by 4.0).


text:
Tag Info

• 341
Accepted

Quadratic Diophantine Equation $x^2 + 2y^2 = 2013$

The equation is not solvable modulo $8$, hence there are no integer solutions. You can see this by considering $x^2\equiv 0,1$ or $4$ modulo $8$ for every $x$.
• 78.4k
Accepted

Solving the nonlinear Diophantine equation $x^2-3x=2y^2$

Multiply through by $4$ and complete the square, $(2x-3)^2 - 8 y^2 = 9,$ so that $(2x-3)^2 + y^2 \equiv 0 \pmod 3.$ It follows that both $(2x-3)$ and $y$ are divisible by $3,$ therefore $x$ as well. ...
• 130k

First 30 solutions of Pell's equation.

Floating point precision is not sufficient for the larger solutions. You should probably look at using a recursive definition for the $k_n$ and $z_n$. They should satisfy $a_{n+2}=18a_{n+1}-a_{n}$ (...
• 4,757
Accepted

Can $n+1$ , $2n+1$ , $3n+1$ all be perfect squares , if $n$ is a positive integer?

If this happens, then $1, n+1, 2n+1, 3n+1$ is a four-term arithmetic progression of perfect squares. But it can be shown (painfully, using elliptic curves, as demonstrated at this link - see Theorem ...
• 113k
Accepted

Prove $(1+\sqrt{2})^k= \sqrt{n}+\sqrt{n-1}$

This follows from $(1-\sqrt{2})^k\,(1+\sqrt{2})^k=(-1)^k$ for every integer $k$. So, if $a_k$ and $b_k$ are integers such that $(1+\sqrt{2})^k=a_k+b_k\sqrt{2}$, then $a_k-b_k\sqrt{2}=(1-\sqrt{2})^k$, ...
• 48.4k
Accepted

• 2,833

• 47.9k

Integer solutions of $y^{2} = 5x^{2} + 17$

Your attempt cannot work, since reducing modulo an integer (here $5$) irreversibly wipes out the distinction between positive an negative numbers; one can never apply arguments based on comparison "...
• 107k

Find all primes $p$ and $q$ such that $p^2-2q^2=1.$

From your last expression we have $$\tag1(p+1)(p-1)=2\cdot[\;2(2d^2+2d)+1\;].$$ If $p=2$ then you get from the original expression that $2q^2=3,$ which is impossible. Therefore $p>2$ and hence $p$ ...
• 3,309

Find all primes $p$ and $q$ such that $p^2-2q^2=1.$

Since $p^2-2q^2=1$, $p$ must be odd. Furthermore, $q$ must be even; if $q$ were odd, then $p^2-2q^2$ would be $3$ mod $4$. Thus, $q=2$ and then $p=3$.
• 326k

General solution of Pell's equation

It's well know that the solution of the Pell's equation satisfy the reccurence relation: $$x_{k+1} = x_1x_k + y_1ny_k$$ $$y_{k+1} = y_1x_k + x_1y_k$$ This was found by Brahmagupta and it holds ...
• 34.9k

How to show that $x^2 - 37y^2 =2$ does not have integer solutions

There are no integer solutions to $$x^2 - 37 y^2 \equiv 2 \pmod 4$$ as $$x^2 - 37 y^2 \equiv x^2 - y^2 \pmod 4$$
• 130k
there are infnitely many postive integer $n$ such $\lfloor \sqrt{7}\cdot n \rfloor=k^2+1(k\in \Bbb{Z})$
I get that there are an infinite number of $n$ such that $\lfloor n\sqrt{d} \rfloor =k^2-1$, not $k^2+1$. However, for $d$ such that there are solutions to $x^2-dy^2 = -3$, such as $d=7$, then there ...


text:
Wellspring - 1 year ago 48
SQL Question

# TSQL Equal or Not Equal conditional in Where clause

Based on a declared variable, is it possible to switch between not equal and equal in the where clause?

For example, if the variable @InState is set to true, then return all the addresses with a state equal to 'CA', if false, return all of the addresses with states <> 'CA'.

Code:

DECLARE @InState bit
SET @InState = 1

SELECT *
WHERE ADDR.Status = 'A'
CASE WHEN @InState = 1
THEN
'CA'
ELSE
''

The ELSE in the code above, returns every state including 'CA'. I need to return every other state, not equal to 'CA'.

I'd try to avoid CASE statements in the WHERE clause and go for something like this;

DECLARE @InState bit
SET @InState = 1

SELECT *
WHERE ADDR.Status = 'A'
AND
(
(@InState = 1
AND ADDR.State = 'CA')
OR
(@InState <> 1
AND ADDR.State <> 'CA')
)

Calculations in a WHERE clause is going to kill your performance by making your query non SARGable;

https://en.wikipedia.org/wiki/Sargable


text:
×

# Whoa! Enrique's streak is at 302 days....

I meant to point this out the day his streak passed 300. Sadly I had a hectic weekend and forgot.

That is an epic streak. May it never end :)

Note by Peter Taylor
2 years, 3 months ago

Sort by:

Hi @Enrique Naranjo Bejarano ! How do you do it? Do you designate a specific time each day to get at least one problem solved? Staff · 2 years, 3 months ago

How do I do it? There isn't any trick, I only solve one problem each day. It have become part of my daily routine. I haven't got a specific time to solve problems. To be honest I don't think that my streak is so impressive because if I have a 300 day streak is because someone in the Brilliant community has added a problem that I have solved for keeping my streak and that it is really very impressive. So I would like to thank the Brilliant community for the great effort for making math and science, in general, available to everyone.

@Finn Hulse You promised that you would eat a rabbit if I got a 300 day streak 😉😂 · 2 years, 3 months ago

Gah you got here before me. I just got back from sleep away camp so I wouldn't have been able to make it anyways. Anyways, congrats @Enrique Naranjo Bejarano! Good luck to @Mursalin Habib who's almost there! :D · 2 years, 3 months ago

Soon @Mursalin Habib will pass @Enrique Naranjo Bejarano , seeing how fast he is keeping his streak! · 2 years, 3 months ago

HAHAHAHAHAHA if only Enrique was going 90% the speed of light... :D · 2 years, 3 months ago

my streak always stay at 1-day!!! · 2 years, 2 months ago

Yay I'm fifth! :D

May the streak ever be with you. · 2 years, 3 months ago

Keeping your streak is easy if you have this set! ;) · 2 years, 3 months ago

@Enrique Congrats in two months you will complete a year. · 2 years, 3 months ago

It's at 303 now O.o Keep it up Enrique! :D · 2 years, 3 months ago

I think I'm on 6th place following Yuxuan seah with 160 day streak. · 2 years, 3 months ago

I think I'm next in the list at 135 days... · 2 years, 3 months ago

I do not obtain see my streak compared with the streak others. I hope that engineers solve this problem.... · 2 years, 3 months ago

Hmmm...try scrolling down the box that includes the people you follow it should list yourself in the list of people with streaks.

Mypoorstreak

If you can't find it there, then it's a bug and we'll put it in our queue to fix. Staff · 2 years, 3 months ago

@Peter Taylor I do not see neither box... the box not appear... · 2 years, 3 months ago

Same. @Peter Taylor · 2 years, 3 months ago


text:
# Proposition 7.2. of Adkins’ Algebra

I don’t understand some of the following text (from Adkins’ Algebra):

1- Why if qq does not divide p−1p-1 then ϕh=1N\phi_h = 1_N (i.e. HH is normal) ? Exercise 11 doesn’t help since it says “… if nh=hnnh=hn …” and not conclude that!

2- If q|p−1q|p-1 why there are nontrivial homomorphisms, especially when in both cases ϕ:Zq→Aut(N)≅Z∗p\phi : Z_q \to Aut(N) \cong Z^*_p?

3- Why b−1abb^{-1}ab have to be in a form of ara^r?! And why rq≡1 mod pr^q \equiv 1 \ mod \ p?

Thank you.

=================

=================

1

=================

(1) There can’t be a nontrivial homomorphism G→HG\to H if |G||G| and |H||H| are coprime. This follows from the first isomorphism theorem (the image is isomorphic to a quotient of GG) and Lagrange’s theorem (which implies quotients of GG have size dividing |G||G|). In particular, if qq and p−1p-1 are coprime (equivalently q∤p−1q\nmid p-1), then the homomorphism Zq→Aut(Zp)\mathbb{Z}_q\to\mathrm{Aut}(\mathbb{Z}_p) must be trivial, since the order of Aut(Zp)\mathrm{Aut}(\mathbb{Z}_p) is just p−1p-1.

(2) If q∣p−1q\mid p-1 then Aut(Zp)\mathrm{Aut}(\mathbb{Z}_p) must have an element of order qq, and then there is a homomorphism which maps Zq\mathbb{Z}_q’s generator to that element of order qq. This will be a nontrivial homomorphism.

(3) If N=⟨a⟩N=\langle a\rangle is normal then bab−1∈⟨a⟩bab^{-1}\in\langle a\rangle. Since all elements of ⟨a⟩\langle a\rangle are of the form ara^r for some exponent rr, that means bab−1=arbab^{-1}=a^r for some rr. (I don’t know why the text is writing the conjugation backwards.) Notice that bab−1bab^{-1} is none other than ϕb(a)\phi_b(a). Applying ϕb\phi_b over and over again is tantamount to conjugating by powers of bb. That is,

ϕb∘⋯∘ϕb⏟n(a)=b(⋯bab−1⋯)b−1=bnab−n=ϕbn(a).\underbrace{\phi_b\circ\cdots\circ\phi_b}_n(a)=b(\cdots bab^{-1}\cdots)b^{-1}=b^nab^{-n}=\phi_{b^{\large n}}(a).

(Of course, ϕnb=ϕbn\phi_b^n=\phi_{b^{\large n}} is just a corollary to the fact that x↦ϕxx\mapsto \phi_x is a group homomorphism.)

But notice that, if ϕb(a)=ar\phi_b(a)=a^r and ϕb\phi_b is itself a group homomorphism, then

ϕb(ϕb(a))=ϕb(ar)=ϕb(a)r=(ar)r=ar2,ϕb(ϕb(ϕb(a)))=ϕb(ar2)=ϕb(a)r2=(ar)r2=ar3,⋮ϕb∘⋯∘ϕb⏟n(a)=ϕb(arn−1)=ϕb(a)rn−1=(ar)rn−1=arn\begin{array}{llll} \phi_b(\phi_b(a)) & = & \phi_b(a^r) & = & \phi_b(a)^r & = &(a^r)^r & = & a^{r^{\large 2}}, \\
\phi_b(\phi_b(\phi_b(a))) & = & \phi_b(a^{r^{\large 2}}) & = & \phi_b(a)^{r^{\large 2}} & = & (a^r)^{r^{\large 2}} & = & a^{r^{\large 3}}, \\
& & & \vdots \\ \underbrace{\phi_b\circ\cdots\circ\phi_b}_n(a) & = & \phi_b(a^{r^{\large n-1}}) & = & \phi_b(a)^{r^{\large n-1}} & = & (a^r)^{r^{\large n-1}} & = & a^{r^{\large n}} \end{array}

In particular, this means ϕbq(a)=arq\phi_{b^q}(a)=a^{r^{\large q}}. But ϕbq(a)=ϕe(a)=a\phi_{b^q}(a)=\phi_e(a)=a. Therefore

(3) is very clear. But I don’t understand (1) and (2), esp. (1). H/ker(د•) \cong Im(د•)H/ker(د•) \cong Im(د•). Then I understand (1) if Im(د•)Im(د•) is either surjective or a subgroup of Aut(Z_p)Aut(Z_p). Is it the case?
– Liebe
Oct 21 at 3:52

1

@Liebe If \phi:G\to H\phi:G\to H is a group homomorphism them \mathrm{Im}(\phi)\mathrm{Im}(\phi) is a subgroup of HH, yes.
– arctic tern
Oct 21 at 3:54


text:
Faça-nos uma visita

Estamos localizados na Rua Tancredo Neves, 219, Conjunto Village Campestre II, Cidade Universitária, Maceió, Alagoas.

Cultos aos domingos: às 09h00 e às 19h00

Reunião de oração e estudo bíblico nas quartas feiras às 19h30

Title

This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text.
This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text.
This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text.
This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text.
This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text.

This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text.
This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text.
This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text.
This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text.
This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text. This is text.


text:
# Reduction from signatures to encryption?

Is it possible to construct an (asymmetric) encryption scheme from a signature scheme?

If the signature scheme is deterministic and allows existential forgery (e.g. RSA), then the answer is yes (create a forgery (m, sig); encrypt plaintexts using AES with sig as the key; send m in clear to the signer along with ciphertexts, who can then compute sig and decrypt these ciphertexts) .

I am interested in similar reductions for probabilistic signature schemes.

What should the properties of a probabilistic signature scheme be so that it can be used for encryption?

-
As an example, DSA seems to be a signature-only scheme. –  Paŭlo Ebermann Jul 16 '11 at 23:12
It would be great if there is a proof of this. –  Jus12 Jul 17 '11 at 15:11
It seems one of the motivation for DSA was to make it hard to use for encryption (as export restrictions on signature schemes are not so strict). –  Jus12 Jul 18 '11 at 4:26

Let's first define a few things. Precise definitions are needed because your question is a bit ill-defined, and it seems that you are somewhat cheating.

Some definitions

Traditionally, we define a signature system as the combination of three algorithms:

• G: key generation; given a "security parameter" t (e.g. the intended key size), yields a key pair (x, y) (x is the private key, y is the public key).

• S: signature generation: given a message m (from a given space of messages M) and x, outputs a signature s.

• V: signature verification: given m, y and s, outputs true or false.

It is supposedly infeasible to do forgeries, i.e., given y but not x, find (m, s) such that V(m, y, s) = true. Existential forgeries are "untargetted" forgeries where the attacker does not get to choose m arbitrarily.

On forgeries and "cheating"

Forgeries are bad, and a signature algorithm which accepts forgeries (existential or not) is considered to be broken. No "standard" signature algorithm accepts existential forgeries. In particular, RSA, as specified by PKCS#1, does not, even when using the "old style" v1.5 padding, which is deterministic: no method is known to generate a number s which, when raised to the public exponent, yields a proper PKCS#1 padding (beginning with 0x00 0x01 followed by eight or more 0xFF bytes). Moreover, the message m is first hashed, and even if you could find a s which produces, when exponentiated, a properly padded hash value, you would still be hard pressed to compute the corresponding m.

So, assuming that you want to apply your method on RSA, you are not talking about "RSA, the signature algorithm"; you need to remove the padding and the hash function, at which point you have the RSA core modular exponentiation, also known as "RSA, the trapdoor permutation". A trapdoor permutation can be used quite immediately for asymmetric encryption. In that sense you are "cheating".

@PulpSpy uses a different cheat, by assuming that he can publish the private key, and keep the public key secret. This may work with RSA, but only if the signature engine (the one which produces the signatures) accepts to work with a "private" key expressed as a raw private exponent and modulus, without knowledge of the modulus factors. "Normal" RSA implementation use the standard private key format, which includes the factors because this speeds up quite a bit private key operations (by a factor of about 4, thanks to the Chinese Remainder Theorem). Also, the "public" key needs to be kept secret, which implies a big exponent, not the usual 3 or 65537; there again, an existing RSA "verifier" implementation may refuse to work.

Rewriting the problem

I suggest the following definition of the problem: let (G, S, V) be a signature system. A key pair is generated; the key holder (Alice) maintains x (the private key) secret, in a box which computes S. The only way to use x is to execute S, which produces a signature on a given message m. The public key y is known by everybody, and Bob has some strong assurance that y is Alice's key through an unspecified mechanism (e.g. a certificate), but there is no other value which is thus unambiguously linked to Alice. Is there a way for Bob to use y in order to convey a confidential message to Alice ?

Note that clause about "no other value". If we allow Alice to publish other data, she could generate a transient key pair for an asymmetric encryption or key exchange algorithm, which Bob would just use (this is how it is actually done in S/MIME when the certificated key of a user is only for signatures). Correspondingly, we are after an asynchronous solution (Bob does all the job in one go, and only then sends the whole to Alice; otherwise, in an interactive protocol, Alice could "cheat" by sending a transient key pair).

For the interest of the exercise, we allow Alice and Bob to input precomputed hash values into S and V: no need to find messages m such that h(m) "works", we accept hand-crafted "hash values" which did not involve a hash computation at all.

With the question stated as above, there is now a good reason why this cannot work with signatures schemes based on a non-interactive zero-knowledge proof. A ZK proof is a protocol in which a prover demonstrates to a verifier knowledge of the solution of a given "problem". The protocol is said to be zero-knowledge because the transcript of the protocol is unconvincing: it is possible, without knowing the actual solution of the problem, to build a fake conversation between a "prover" and a "verifier", and there is no way to distinguish between a fake conversation and a real conversation with the true prover. In that sense, no information about the secret data leaks to the outside. A ZK protocol can be turned into a signature scheme: in a normal ZK protocol, the prover sends one or several commitments, then the verifier sends a challenge, to which the prover can respond in a way which is satisfying with regards to the committed values. It "suffices" to compute the challenge from the commitments using an appropriate one-way function, to make the protocol non-interactive; if a message is also used as additional input to the one-way function, then we have a signature algorithm.

This category of signature algorithm includes all the discrete logarithm-based signature schemes: ElGamal signatures, DSA, ECDSA, Schnorr... (they actually use a slightly weakened variant of ZK dubbed "computational zero-knowledge" because their ZKness is relative to the hardness of some operation, here the discrete logarithm).

The point of the ZK property is that producing the signature leaks no information about the signature key, except that the signing box knows it. For an asymmetric encryption or key exchange scheme, Alice must be able to extract at least one bit of extra information from is signing black box. Here, everybody knows that Alice owns the private key, and any signature generated by S will say nothing more. Therefore, there is nothing that Alice can do with S and what Bob sent her, that will yield any information suitable for a key exchange.

Rewriting this as a properly formal proof looks like hard work. So, right now, what I wrote above is merely "intuition". It means that I find it improbable that one could find a (non-cheating) way of turning an ECDSA-signing-box into a key exchange mechanism.

-
Nice answer. I agree with your caveats regarding my cheat and RSA. (I have a few comments when at keyboard not on my phone). –  PulpSpy Jul 17 '11 at 21:52
I guess someone would have written a paper on it. If not, it is a good topic for one. –  Jus12 Oct 3 '11 at 7:29

In principle, the answer is no, with an asterisk. Signature schemes are equivalent to one-way functions under black-box reductions. Public-key encryption scheme implies the existence of key agreement.

Impagliazzo & Rudich famously proved that there is no black-box reduction from one-way functions to key agreement. That means there is no subroutine-respecting way of transforming a one-way function (equivalently, a signature scheme) into a key agreement scheme. They have not ruled out the possibility of a very clever way to use the code of a signature scheme to construct a key agreement scheme, but this seems highly unlikely (not to mention that such techniques are typically highly impractical).

Note: FYI, I originally answered this having misread the question to refer to symmetric-key encryption. In that case, the answer is yes:

Any signature scheme can be converted in a black-box way to yield a symmetric-key encryption scheme. Both of the two primitives are equivalent to one-way functions under black-box reductions.

One way to do it:

1. A signature scheme yields a one-way function in a very straight-forward way. More specifically, the following function is one-way: on input $x$, interpret $x$ as random coins to give as input to the key generation algorithm of the signature scheme. Give the resulting verification key as output of the (one-way) function.

2. A one-way function yields a pseudorandom function, using the GGM construction.

3. A pseudorandom function $f$ yields a symmetric-key encryption scheme in a very easy way. Let $s$ be the secret. Then to encrypt a message $m$, choose a random $r$ and give $(r, n \oplus f(s,r))$ as the ciphertext.

3a. If you don't like that, you could instead plug the pseudorandom function into a Feistel network (Luby-Rackoff construction) to obtain a strong pseudorandom permutation (i.e., a block cipher) and use a good block cipher mode.

MACs can also be constructed from one-way functions, so you can pretty much get any kind of symmetric-key cryptography, and symmetric-key CCA security is no barrier.

Interestingly, nothing about this construction uses the signing algorithm -- just the asymmetry of the signature scheme's key generation is enough.

-

Chaffing and Winnowing creates a symmetric encryption scheme from a symmetric MAC:

http://people.csail.mit.edu/rivest/chaffing-980701.txt

I suppose you could apply the same technique to your problem—send each bit of your message separately, obscured by the presence of chaff, and send signatures indicating which are the message bits. This assumes that the public (verification) key is secret and known only to the intended recipient and that you can't tell which bits have valid signatures on them without it.

Warning: this is just off the cuff—I haven't thought this through very much.

-
This won't work. The public verification key is public, so I am talking specifically about signatures, not MACs. But thanks for the answer :) –  Jus12 Jul 17 '11 at 7:32
@Jus12: At the end there is a paragraph mentioning "designated verifier signatures", which could work here. –  Paŭlo Ebermann Jul 17 '11 at 11:27
@Zooko: Interesting read, even if it does not really answer the question. –  Paŭlo Ebermann Jul 17 '11 at 11:29
@Paulo: hmm yes Designated verifier signatures are a different beast. They might work. Though the question was motivated from DSA. –  Jus12 Jul 17 '11 at 15:11
@Zooko, Paolo: yes, the last para does elude to "designated verifier signatures" (DVS), which might work. The only issue is that DVS require the knowledge of verifiers or share a secret with them. –  Jus12 Jul 18 '11 at 11:58

First in response to your example. In proving a encryption scheme is secure, you have to assume that an adversary has at least as much computational power as the participants. Therefore if Alice is sending a message to Bob, and Alice can find a forgery, then the adversary can as well. Since the signature is deterministic, the adversary now has the key and can decrypt the messages. (You could argue that Alice's forgery is easier to find since she chooses the message and so it may be secure in a gap group where existential is easy and selective is hard.)

Next, there are different types of reductions. I will use a blackbox reduction. This means we use the signature/verification functions without any knowledge of how they work but we are allowed to supply wrong inputs to the functions: for example, submitting a key where we should a message or submitting a signing key where we should use a verification key.

A public key encryption scheme can be built from a blackbox non-deterministic signature scheme as follows:

• Bob generates a signing key and verification key.
• Bob makes the signing key public and the verification key private (opposite of typical).
• Alice takes her message and will encrypt it bit-by-bit.
• Alice takes the first bit.
• If it is 0: Alice generates a random string, signs the string with Bob's key, and outputs the string and signature.
• If it is 1: Alice generates a random string, generates a fake signature, and outputs the string and fake signature.
• Bob receives the pairs of strings and uses his private verification key to see if the signatures are valid (decrypts a 0) or invalid (decrypts a 1).

Informally, an adversary has two lines of attack. One is to see if the pairs of strings are valid, however assuming the signature scheme is secure, this will not work without the verification key (see fineprint). The second is to sign the strings with the signing key and see if the signatures match what Alice sent. This will not work because the signature is randomized and the signatures will overwhelmingly never match.

Fineprint: my signature scheme assumes there is a verification key and without the key, you cannot verify the signature. This is not the case for all signature schemes, in particular ones based on pairings (eg BLS) where verification is public and does not require a key. On second thought, it is not even the case for DSA where the verification key is easily computed from the signing key. I guess it only works for RSA (and similar) signatures.

-
(1) Keeping the signing key public may enable computation of verification key directly (at least it cannot be proved that it would not). Let (G, S, V) be a signature scheme, with usual meanings, now consider the modified scheme (G', S', V') as: G' = G, S' = (S, V), V' = V. Then the above idea does not work. (2) Alice does not send the forgery to Bob . Rather she uses the forgery (forged signature) as a secret key and only sends the message on which the forged signature was created. Using this message, Bob could compute the same forged signature, which can now act as a symmetric encryption key. –  Jus12 Jul 17 '11 at 15:14
(1) Right it is not a reduction from any signature scheme, only ones with the condition that verification is not possible without the verification key. See fine print. (2) the adversary seeing the message only can make a selective forgery and obtain the same signature, assuming forgeries are easy and signature is deterministic. It only works under assumption that existential is easy and selective is hard. –  PulpSpy Jul 17 '11 at 21:37

Wait, is the goal for Bob to encrypt messages to Alice (who holds the secret signing key) or for Alice to encrypt messages to Bob (who knows Alice's public key)? If it is the former, then I can't think of any way around Thomas Pornin's excellent argument above. If it is the latter, and if we grant my assumption that nobody else apart from Bob knows Alice's public key, then my proposal above based on Chaffing And Winnowing might work.

-
You could have added this as a comment, or as an edit to your question. It is not really an answer, I think. –  Paŭlo Ebermann Aug 3 '11 at 21:32


text:
# Efficiently computing with pullbacks and pushouts

Often when computing in category theory, one has to show that some square is cartesian. Depending on the number of maps involved, and their arrangement, it's somewhat difficult to write down exactly all of the relationships between the various squares.

We have a commutative diagram

$$\begin{matrix}C_3 &\to& C_2 &\to& C_1\\ \downarrow&&\downarrow&&\downarrow\\ D_3&\to &D_2&\to& D_1 \end{matrix}$$

Label the right vertical map $p$, and assume we further have a commutative diagram

$$\begin{matrix}\ast &\to& C_1\\ \downarrow&&\downarrow\\ D_3&\to& D_1 \end{matrix}$$

Where map on the top of the square is called $x$ (it classifies a point $x$, and the left vertical map is called $\sigma$. The bottom map and right map are the same maps from the first diagram $D_3\to D_1$ is simply the composite of the two bottom maps in the first diagram.

We would like to show that the canonical map between fibers $$C_3\times_{D_3\times_{D_1} C_1} \{\sigma,x\}\to C_2\times_{C_1} \{x\}\times_{D_2\times_{D_1} \{px\}}\{e\}$$ is a pullback of the canonical map $C_3\to C_2\times_{D_2} D_3$ (if you really care to know, this is to show that the first map is a trivial fibration, since we knew at the time that the second map was a trivial fibration).

Note: The vertex $\{e\}$ is the image of $\sigma$ in $D_2$.

The diagram I drew to realize this was a sheet of four cartesian squares with a cartesian cube attached at the top left square. This is before even taking fibers.

Another example: If anyone's following Ravi Vakil's notes for his schemes course, there is a similar, albeit substantially less complicated problem to prove that the "magic square" is cartesian. I did a similar computation, which ended again with the surprising cartesianness ultimately arising from a cartesian cube attached to a cartesian sheet.

Then the question: Is there a more efficient way to verify claims like this (i.e. without drawing out "every single possible pullback"?

-
When I was writing up my thesis I had to think a lot about moduli problems in algebraic geometry and I ended up with questions like this, and once or twice an even simpler sort of question: I had some crazy commutative diagram and I wanted to use some universal property of some subset of it (e.g. "this bit is a pullback of this bit so there's a map from here to here that makes this triangle commute") to draw in another arrow, and I wanted to verify that the new diagram was a commutative diagram! The first time I ran into this issue I had to think hard about what the correct definition... –  Kevin Buzzard Sep 18 '10 at 9:55
...of "commutative diagram" was, and then I had to think about what one actually needed to check in order to verify that adding an arrow to a commutative diagram made a new commutative diagram: "I know this new triangle commutes, but do I also have to check that this pentagon does or is it a formal consequence? Do I even have to check that every closed loop mentioning the new arrow commutes? No hang on, that doesn't always make sense...um..." sort of thing. So I agree that it can get very confusing! There's nothing deep though, it's just a matter of practice (in my experience). –  Kevin Buzzard Sep 18 '10 at 9:57

Try doing it in sets; then you can usually write it out "syntactically". It looks like you've got a map $$\{c_3\in C_3|p(c_3)=\sigma, fg(c_3)=x\} \to \{c_2 \in C_2| f(c_2)=x \}$$ sending $c_3\mapsto g(c_3)$ and you want to know it's the pullback of the map $$\{c_3\in C_3\} \to \{(c_2,d_3)| p(c_2)=g(d_3)\}$$ sending $c_3\mapsto (g(c_3),p(c_3))$. I'm writing "$p$" for all vertical maps, "$g$" for $C_3\to C_2$ and $D_3\to D_2$, and "$f$" for $C_2\to C_1$ and $D_2\to D_1$.

Having done this, your claim looks false: it looks like the pullback set is just $\{c_3\in C_3|gf(c_3)=x\}$. But quite possibly I've misinterpreted your diagrams.

The point of this exercise is that, if the set theoretic argument holds, then you can prove the version in the category $C$ using the Yoneda lemma; apply $\mathrm{Hom}_{\mathcal{C}}(T,{-})$ to everything, for arbitrary objects $T$, and observe you get a pullback of sets, therefore you must have a pullback in $\mathcal{C}$.

-
I changed the square brackets to curly braces, as you mentioned. –  Tom Church Sep 18 '10 at 2:37
The claim I'm referencing is correct (it's from a book, and I verified it by hand), but I may not have included all of the necessary information. I think that you misunderstood precisely what we wanted prove, namely that one map is the pullback of another map by a third map (To see the claim in its full glory, look at the discussion before Proposition 2.4.4.2 (about the existence of the fibre sequence)). Anyway, your idea is really good! –  Harry Gindi Sep 18 '10 at 10:19
Tom's solution is the one that I was going to suggest as well. He beat me to it :-) –  Tim Porter Sep 18 '10 at 14:17
Yes, but it was Charles's solution! –  Harry Gindi Sep 18 '10 at 15:46
This answer is lovely, and also generalises well. In logical terms, it shows that you can use algebraic equational logic with equality to reason in categories with finite limits; in the jargon, this logic is a sound internal language for such categories. If the category has more structure, then you can do this with a more powerful logic: e.g. if the category has well-behaved images (i.e. is regular), you can use existential quantifiers as well in your reasoning. The beginning of the chapter on Logic in the Elephant has an excellent survey of these techniques. –  Peter LeFanu Lumsdaine Sep 18 '10 at 20:56


text:
# Lesson 14: Evaluating Expressions with Exponents

Let’s find the values of expressions with exponents.

## 14.1: Revisiting the Cube

Based on the given information, what other measurements of the square and cube could we find?

GeoGebra Applet ftGcrgJ5

## 14.2: Calculating Surface Area

A cube has side length 10 inches. Jada says the surface area of the cube is 600 in2, and Noah says the surface area of the cube is 3,600 in2. Here is how each of them reasoned:

$6 \boldcdot 10^2$
$6 \boldcdot 100$
$600$

Noah’s Method:

$6 \boldcdot 10^2$
$60^2$
$3,\!600$

Do you agree with either of them? Explain your reasoning.

## 14.3: Expression Explosion

Evaluate the expressions in one of the columns. Your partner will work on the other column. Check with your partner after you finish each row. Your answers in each row should be the same. If your answers aren’t the same, work together to find the error.

$5^2+4$

$2^4 \boldcdot 5$

$3 \boldcdot 4^2$

$20+2^3$

$9 \boldcdot 2^1$

$\frac19 \boldcdot \left( \frac12 \right)^3$

$2^2+25$

$2^3 \boldcdot 10$

$12 \boldcdot 2^2$

$1+3^3$

$3 \boldcdot 6^1$

$\frac18 \boldcdot \left( \frac13 \right)^2$

## Summary

Exponents give us a new way to describe operations with numbers, so we need to understand how exponents get along with the other operations we know.

When we write $6 \boldcdot 4^2$, we want to make sure everyone agrees about how to evaluate this. Otherwise some people might multiply first and others compute the exponent first, and different people would get different values for the same expression!

Earlier we saw situations in which $6 \boldcdot 4^2$ represented the surface area of a cube with side lengths 4 units. When computing the surface area, we evaluate $4^2$ first (or find the area of one face of the cube first) and then multiply the result by 6. In many other expressions that use exponents, the part with an exponent is intended to be evaluated first.

To make everyone agree about the value of expressions like $6 \boldcdot 4^2$, the convention is to evaluate the part of the expression with the exponent first. Here are a couple of examples:

\begin {align} &\;6 \boldcdot 4^2\\ &= 6 \boldcdot 16\\&= 96 \end {align}

\begin {align} &\;45 + 5^2\\ &= 45 + 25\\&= 70 \end {align}

If we want to communicate that 6 and 4 should be multiplied first and then squared, then we can use parentheses to group parts together:

\begin {align} &\;(6 \boldcdot 4)^2\\ &= 24^2\\&= 576 \end {align}


text:
# Dictionary:Convolution

Other languages:
English • español

(kon, v∂ loo’ sh∂n) Change in waveshape as a result of passing through a linear filter.

1. A mathematical operation between two functions, g(t) and f(t), often symbolized by an asterisk:

${\displaystyle g(t)\ast f(t)=\int _{\tau }g(\tau )f(t-\tau )d\tau }$.

Convolution is not restricted to one dimension. For example, in two dimensions,

${\displaystyle g(x,y)^{\ast }f(x,y)=\int _{\alpha }\int _{\beta }g(\alpha ,\beta )f(x-\alpha ,y-\beta )d\alpha d\beta }$.

2. Linear filtering. If a waveform g(t) is passed into a linear filter with the impulse response f(t), then the output is given by the convolution of g with f. In discrete form where the input is a series of impulses of varying size, each will generate an f(t) of proportional amplitude and the output will be the superposition of these. This can be expressed as

${\displaystyle g_{t}\ast f_{t}=\sum _{k=0}^{L}g_{k}f_{t-k}}$.

This expresses that the output of a linear filter at the instant t is a weighted linear combination of the inputs. L is the convolution operator length and (L+1) is the number of points in the operator. (A simple computer program is shown in Figure F-14.) The frequency-domain operation equivalent to time-domain convolution consists of multiplying frequency-amplitude curves and adding frequency-phase curves. Convolution is sometimes done by (a) replacing each spike of the input with a proportionately scaled version of the impulse response and superposition forms the output; (b) folding where the impulse response of the filter is reversed in time and slid past the input, the output for each position of the impulse response being the sum of the products of input and folded impulse response for corresponding points; (c) multiplying z-transforms of the input and of the impulse response to give the z-transform of the output; or (d) multiplying Fourier or Laplace transforms to give the Fourier or Laplace transform of the output. See Sheriff and Geldart (1995, 279-81 and 540-2). Well logs may be thought of as the convolution of the response of the earth adjacent to the borehole with the logging sonde impulse response.

3. Convolution in two dimensions is used with gravity, magnetic, and other data to produce grid residual, second derivative, continuation maps, etc. see Fuller (1967).


text:
# solving the Black-Scholes PDE by finite differences

This entry presents some examples of solving the Black-Scholes partial differential equation in one space dimension:

 $\displaystyle rf=\frac{\partial f}{\partial t}+rx\frac{\partial f}{\partial x}% +\tfrac{1}{2}\sigma^{2}x^{2}\frac{\partial^{2}f}{\partial x^{2}}\,,\quad f=f(t% ,x)\,,$

over the rectangle $0\leq t\leq T$, $X_{\mathrm{L}}\leq x\leq X_{\mathrm{U}}$, with various boundary conditions on the top, bottom, and right sides of the rectangle. The parameters $r$, $\sigma>0$ are arbitrary constants.

The partial differential equation can be solved numerically using the basic methods based on approximating the partial derivatives with finite differences.

## 0.1 Finite-difference formulae

We summarize the equations for the finite differences below.

Let $n$, $m$, $k$ be some chosen positive integers, which determine the grid on which we are approximating the solution of the PDE.

Set $u_{i,j}$ to be the approximation to $f(T-i\Delta t,j\Delta x)$, for $0\leq i\leq m$ and $k\leq j\leq k+n+1$. (For convenience, we have made time move “backwards” as we increase $i$, because the original PDE is really a backwards heat equation, and evolves backwards in time.)

Also set:

 $\Delta t=\frac{T}{m}\,,\quad\Delta x=\frac{X_{\mathrm{U}}-X_{\mathrm{L}}}{n+1}$

Explicit method.

 $\displaystyle\frac{u_{i+1,j}-u_{i,j}}{\Delta t}$ $\displaystyle=-ru_{i,j}+rj\Delta x\,\frac{u_{i,j+1}-u_{i,j-1}}{2\Delta x}$ $\displaystyle\qquad+\frac{1}{2}\sigma^{2}(j\Delta x)^{2}\,\frac{u_{i,j-1}-2u_{% i,j}+u_{i,j+1}}{\Delta x^{2}}$
 $\displaystyle u_{i+1,j}$ $\displaystyle=\Bigl{(}\tfrac{1}{2}(\sigma j)^{2}\Delta t-\tfrac{1}{2}rj\Delta t% \Bigr{)}\,u_{i,j-1}$ $\displaystyle+\Bigl{(}1-(\sigma j)^{2}\Delta t-r\Delta t\Bigr{)}\,u_{i,j}$ $\displaystyle+\Bigl{(}\tfrac{1}{2}(\sigma j)^{2}\Delta t+\tfrac{1}{2}rj\Delta t% \Bigr{)}\,u_{i,j+1}\,.$

Since the PDE to solve is parabolic and time-dependent, we can step through time to numerically approximate it. Given $u_{i,*}$, we can recursively compute $u_{i+1,*}$.

(Add stencil of numerical method here…)

Implicit method.

 $\displaystyle\frac{u_{i+1,j}-u_{i,j}}{\Delta t}$ $\displaystyle=-ru_{i+1,j}+rj\Delta x\,\frac{u_{i+1,j+1}-u_{i+1,j-1}}{2\Delta x}$ $\displaystyle\qquad+\frac{1}{2}\sigma^{2}(j\Delta x)^{2}\,\frac{u_{i+1,j-1}-2u% _{i+1,j}+u_{i+1,j+1}}{\Delta x^{2}}$
 $\displaystyle u_{i,j}$ $\displaystyle=\Bigl{(}-\tfrac{1}{2}(\sigma j)^{2}\Delta t+\tfrac{1}{2}rj\Delta t% \Bigr{)}\,u_{i+1,j-1}$ $\displaystyle+\Bigl{(}1+(\sigma j)^{2}\Delta t+r\Delta t\Bigr{)}\,u_{i+1,j}$ $\displaystyle+\Bigl{(}-\tfrac{1}{2}(\sigma j)^{2}\Delta t-\tfrac{1}{2}rj\Delta t% \Bigr{)}\,u_{i+1,j+1}\,.$

Crank-Nicolson method.

 $\displaystyle\Bigl{(}-\tfrac{1}{4}(\sigma j)^{2}\Delta t+\tfrac{1}{4}rj\Delta t% \Bigr{)}u_{i+1,j-1}\\ \displaystyle+\Bigl{(}1+\tfrac{1}{2}(\sigma j)^{2}\Delta t-\tfrac{1}{2}r\Delta t% \Bigr{)}u_{i+1,j}+\Bigl{(}-\tfrac{1}{4}(\sigma j)^{2}\Delta t-\tfrac{1}{4}rj% \Delta t\Bigr{)}u_{i+1,j+1}\\ \displaystyle=\Bigl{(}\tfrac{1}{4}(\sigma j)^{2}\Delta t-\tfrac{1}{4}rj\Delta t% \Bigr{)}u_{i,j-1}+\Bigl{(}1-\tfrac{1}{2}(\sigma j)^{2}\Delta t-\tfrac{1}{2}r% \Delta t\Bigr{)}u_{i,j}\\ \displaystyle+\Bigl{(}\tfrac{1}{4}(\sigma j)^{2}\Delta t+\tfrac{1}{4}rj\Delta t% \Bigr{)}u_{i,j+1}$

## 0.2 Convergence of methods

(Briefly discuss convergence properties of these methods here…)

## 0.3 Example results

Boundary conditions and parameters:

 $\displaystyle r=0.10\,,\quad\sigma=0.40\,,\quad T=0.5\,,\quad K=50.00\,.$ $\displaystyle X_{\mathrm{L}}=0\,,\quad X_{\mathrm{U}}=100.00\,.$ $\displaystyle\quad m=100\,,\quad n=200\,,\quad\Delta t=0.005\,,\quad\Delta x=0% .4975\,.$
 $\displaystyle f(T,x)$ $\displaystyle=\max(x-K,\>0)\,,$ $\displaystyle X_{\mathrm{L}}\leq x\leq X_{\mathrm{U}}$ $\displaystyle f(t,0)$ $\displaystyle=0\,,$ $\displaystyle 0\leq t\leq T\,,$ $\displaystyle f(t,X_{\mathrm{U}})$ $\displaystyle=x-Ke^{-r(T-t)}\,,$ $\displaystyle 0\leq t\leq T\,.$

(Describe analytic solution here…)

 $\displaystyle r=0.10\,,\quad\sigma=0.40\,,\quad T=0.5\,,\quad K=50.00\,.$ $\displaystyle X_{\mathrm{L}}=0\,,\quad X_{\mathrm{U}}=100.00\,.$ $\displaystyle\quad m=100\,,\quad n=200\,,\quad\Delta t=0.005\,,\quad\Delta x=0% .4975\,.$
 $\displaystyle f(T,x)$ $\displaystyle=\max(x-K,\>0)\,,$ $\displaystyle X_{\mathrm{L}}\leq x\leq X_{\mathrm{U}}$ $\displaystyle f(t,0)$ $\displaystyle=0\,,$ $\displaystyle 0\leq t\leq T\,,$ $\displaystyle f(t,X_{\mathrm{U}})$ $\displaystyle=0\,,$ $\displaystyle 0\leq t\leq T\,.$
• http://svn.gold-saucer.org/math/PlanetMath/SolvingTheBlackScholesPDEByFiniteDifferences/bss.pyPython program that implements the finite-difference methods for the above two problems, and plots the results

Title solving the Black-Scholes PDE by finite differences SolvingTheBlackScholesPDEByFiniteDifferences 2013-03-22 16:30:59 2013-03-22 16:30:59 stevecheng (10074) stevecheng (10074) 6 stevecheng (10074) Example msc 65M06 msc 91B28 msc 35K15


text:
## Precalculus (6th Edition) Blitzer

Step 1. Graph the function as shown in the figure. Step 2. We can identify the function as a parabola with a vertex at $(1,-4)$ which is also a minimum.