Please HELP! Carl Gauss Algorithm for getting Easter on specified year JAVA - Algorithms Discussion Boards

I am developing a billing software for a Water Company would someone out there help in the algorithm for calculating the amount to pay based on the logic below am using vb.net.

The Company has set tarrifs which are

Consumption Amount Per Consumption
0-10 12
10-20 33
20-40 44
40-100 56
over 100 64

if a client consumes less than 10 units he pays the minimum which is 120

if a client for Example consumes say 110 units the amount is calculated as follows

0 -10 ten units are used hence amount to pay will be 10*12 =120
100 units will remain

10 -20 ten units are again used hence the amount will be 10*33 =330
total amount will be 120 +330 = 450
90 units remain
20-40 twenty units are used hence amount will be 20 * 44 =880
total amount will be 120+330+880 =1330
70 units remain
40 -100 60 units will be used hence amount will be 60 * 56 =3360
total amount will be 120+330+880+3360=4690

10 units remain

over 100 10 * 64 =640

total amount = 4690 +640 = 5330

briogene

You've clearly described the algorithm in this post. Now do your own homework.

--
If you view money as inherently evil, I view it as my duty to assist in making you more virtuous.

Sometimes a person has a mental block, and just has to see someone else's solution before the clouds begin to clear. And then some of it is just experience. When he has been programming as long as I have, solving problems like this will probably be second nature to him. I've worked with programmers for years now, and I see folks struggle with these kinds of (seemingly simple) problems all the time.

Then again, sometimes I struggle with (seemingly simple) problems, and a bit of insight from a coworker is greatly appreciated.

David

Your algorithm looks suspicious to me. Please verify (just for peace of mind) that the more you use, the more expensive each successive unit is.

I don't work with utilities, and perhaps this is completely correct. It is just counter to my free-market thinking, where, the more you buy, the cheaper each succeding unit is...

static int tarrifAmounts[] = {0, 10, 20, 40, 100, INT_MAX};
static int tarrifRates[] =   {0, 12, 33, 44, 56,  64};

int bill( int amount )
{
   int ret = 0;
   int tindx = 1;
   while( amount > tarrifAmounts[tindx] )
   {
      ret += tarrifRates[tindx] * (tarrifAmounts[tindx]-tarrifAmounts[tindx-1]);
      tindx++ ;
   }
   ret += tarrifRates[tindx] * (amount - tarrifAmounts[tindx-1]);
   return ret;
}

Convert it to VB, check whether it works, and send my payment to ...

Wink | ;)

David

-- modified at 16:54 Monday 22nd October, 2007
OOPS: I just noticed that you said there is a minumum charge. Therefore, the actual billing amount will need to be:
max(MINIMUM_CHARGE, bill(amountUsed))
Or just embed it into the bill algorithm. Whatever works for you.

Thanks This really works Smile | :)

You're welcome.

How handsome does this form need to look, you can do all the math in the push of a button while showing the total bill hours and the total price ONLY or you can break it down into the different levels and show the sub totals of each as you have explained.

I would perform the over 100 math first then deal with everything under 100, in your case 10, 10, 20, 60. The code can be a tad long hand so others can figure it out later in your absence or transfer or move on to a different job, like the boss who may not be an old VB Head. The code can be written after your psuedo code using If Then statements or If Then Else.

Do you already have a form made up, whats on it, I would make it as busy as possible, maybe 7 textboxes, 7 labels, 1 button for the math, but code out each box as in your psuedo code and the button will perform it all and show the TOTAL AMOUNT OWED based on the HOURS CONSUMED.

I just built an excel spreadsheet with the minimum amount of numbers to go from say 23 thru 150, I only used like 7 numbers, like 28 + 36 = 64 or 25 + 32 + 40 = 97, by using these few numbers thru my upper limit I could combine them to get any total from 23 thru 150 inclusive, the maximum of additions would be 5 of my 7 such as 25 + 25 +......= 150.

EDIT, SINCE I LIVE IN A FORIEGN COUNTRY, THE US DOLLAR TO YEN CHANGES DAILY AND WE HAVE CHARTS TO SHOW AT AN INSTANT WHAT YOU WILL GET FOR THE AMOUNT YOU ARE GOING TO EXCHANGE.

I think what I am trying to say is that you should also create a table that will show every combonation from zero (0.01) hours usage thru a FINITE 'n' upper limit or infinite limit, excel will knock that out in seconds for the usage numbers over 100 since the rate does not change over 100.

Are you going to link this all to a spreadsheet or to SQL database, put customer info on form1 and make it busier than I stated above, thats good too.

As you say, you cant see the forest for the trees, this should be an easy one, just depends on how you want it to look and how long do you want the code, even the longest will print out on one sheet of paper.

The more electric you use, the more those people pay, sound like VA disability math being used here.

So so far I'm trying to implement a class. I can do that alright but I'm having trouble with the methods. I read his algorithm something like this:

1. Let y be the year(such as 1800 or 2001).
2. Divide y by 19 and call the remainder a. Ignore the quotient.
3. Divide y by 100 to get a quotient b and a remainder c.
4. Divide b by 4 to get a quotient d and a remainder e.
5. Divide 8 * b + 13 by 25 to get a quotient g. Ignore the remainder.
6. Divide 19 * a + b - d - g + 15 by 30 to get a remainder h. Ignore the quotient.
7. Divide c by 4 to get a quotient j and a remainder k.
8. Divide a + 11 * h by 319 to get a quotient m. ignore the remainder.
9. Divide 2 * e + 2 * j - k - h + m + 32 by 7 to get remainder r. Ignore the quotient.
10. Divide h - m + r + 90 by 25 to get a quotient n. Ignore the remainder.
11. Divide h - m + r + n + 19 by 32 to get a remainder p. Ignore the quotient.

For the program I input 2001 and it gave me back n=4 and p=17
It's supposed to give back n=4 and p=15.

Here are the equations I wrote:

public int getEasterSundayMonth(int y)
{
double a = y % 19;
int b = (int) y/19;
double c = y % 100;
int d = (int) b/4;
double e = b % 4;
int g = (int) ((8 * b) + 13)/25;
double h = ((19 * a) + b - d - g + 15) % 30;
int j = (int) c/4;
double k = c % 4;
int m = (int) ((a + 11) * h)/319;
double r = ((2 * e) + (2 * j) - k - h + m + 32) % 7;
int n = (int) (h - m + r + 90)/25;
return n;
}

public int getEasterSundayDay(int y)
{
double a = y % 19;
int b = (int) y/19;
double c = y % 100;
int d = (int) b/4;
double e = b % 4;
int g = (int) ((8 * b) + 13)/25;
double h = ((19 * a) + b - d - g + 15) % 30;
int j = (int) c/4;
double k = c % 4;
int m = (int) ((a + 11) * h)/319;
double r = ((2 * e) + (2 * j) - k - h + m + 32) % 7;
int n = (int) (h - m + r + 90)/25;
int p = (int) (h - m + r + n + 19) % 32;
return p;

Please help me find out what's wrong. I kind of don't understand, I do realize that this site is filled more with C and C++, but hopefully you guys can help me out.

Have you tried debugging it? Single step through the code and check that each line produces what you expect.

Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."

Oh hey thanks that helped. I ended up finding out that I wrote:

int b = (int) y/19-when it was supposed to be "y/100."

I'm looking for some algorithm to help me in plotting large amount of data.

The situation is like this: I have some experimental data points that I want to show in a window, and I want to be able to zoom everywhere in the graph. The data have been recorded for 1 to 2 hours at 10 kHz, so each graph would have 30-70 million points in it.

Of course plotting ALL of the point is way too slow (and quite pointless), so my first -a bit naive- approach to the problem was to plot a point every x, where x depends on the zoom level, eventually plotting each point at very high zoom levels. This works fine but it has a majour problem: these plots, in fact, are not uniform, they have "spikes" that last few milliseconds and I'm interesting in seeing these events at all zoom level (so that I can select that area and zoom into it).

Any idea on how to get around this? Unsure | :~

Thanks in advance
nico

You could try an algorithm that HP used to use in their Spectrum Analyzers. Take whatever range of data you want to plot, say 1 million points, and map this to say 1000 plot points. They would divide the x-axis up into 500 bins of 2000 points each, and in each bin they would determine the max and min value of the 2000 samples. They would then plot the 1000 points min1, max1, min2, max2, min3, max3, ... where {min1, max1} are the min and max values in the first bin etc. If the number of bins you use is greater than the number of pixels across your display then you won't be able to see any difference between the sampled graph and the original one. So visually this looks identical to plotting all the data, but it will plot / update much much faster. Of course if you zoom in significantly you have to recalculate the bins and the max/mins otherwise you will see the sampling artifacts.

Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."

That sounds good! I'll try it, thanks!

nico

I implemented the solution you suggested and it seems to work really well!
I just have to fine-tune it a little bit for my particular application but it's a very good start!
Thanks a lot!

nico

You're welcome Smile | :)

Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."

I like that approach! Laugh | :laugh:

ROFLOLMFAO

A long-lost text by the ancient Greek mathematician shows that he had begun to discover the principles of calculus.[^]

"There are II kinds of people in the world, those who understand binary and those who understand Roman numerals." - Bassam Abdul-Baki

Web - Blog - RSS - Math - LinkedIn - BM

I saw a PBS show about this very thing over a year ago. I've been wondering how much more advanced we would be right now if that knowledge had passed down through the ages?

Unfortunately, we'll never know. But in this case, it wasn't religion's fault. Poke tongue | ;-P

"Dissent is the highest form of patriotism." - Thomas Jefferson

Web - Blog - RSS - Math - LinkedIn - BM

Is there an efficient algorithm to fill memory with an arbitrary pattern?

void memoryfill( void* target, char* pattern, size_t patlen, size_t numRepeats )
{
   if( 1 == patlen ) memset(target, *pattern, numRepeats);
   else ???
}

I came up with something that makes 2*log(numRepeats) calls to memcpy(), but figured this must be a standard thing to do, and there is probably a good algorithm (better than mine?) already out there. I couldn't find anything on CodeProject, or on Google.

David

I wasn't getting any responses, so I went ahead an posted my O(log(n)) solution at http://www.codeproject.com/script/comments/forums.asp?forumid=1647&XtraIDs=1647&sd=13+Jul+2007&ed=11+Oct+2007&author=jay_p_patel&stype=1&select=2267440&mpp=50&fr=167&df=100#xx2267440xx[^]. Perhaps there is not a textbook algorithm for this, and if not, then maybe my algorithm will help someone.

David

You can use destructive overlap to write your fill pattern as fast as your CPU can go. Here's the algorithm:

1. Copy one instance of the pattern to target.
2. Copy memory from target to (target + patlen) with length (numRepeats - 1) * patlen. (This is one function call.)

I believe this is the most efficient algorithm possible. The implementation of memcpy will probably be more efficient than anything you could write in a higher-level language. Also you're copying from addresses you just wrote to, so they'll already be in the cache. This lets the CPU avoid getting these bytes from (relatively) slow external memory chips. This algorithm should fly like the wind!

IF (a few critical things...) then I think you're right. I think your algorithm will work really really good. I'm working on other things, and don't really want to write a timing test, but I believe you're probably right about it being the fastest possible algorithm.

Now for the critical things:
IF memcpy copies from the end of the array instead of from the base, this algorithm won't work at all. Depending on how it computes the target (if copying from the end), it'll either copy garbage until it finally hits the first pattern, and then make one good copy of it, or it'll make one good copy first, then cause a GPF by attempting to overwrite memory to the left of the src. Here's a quote from "STANDARD C" by P.J. Plauger and Jim Brodie regarding memcpy: "The elements of the array can be accessed and stored in any order." It could even start in the middle of the array if that favors the target environment.

I suppose one could bracket the code with #if's, assuming one could absolutely determine how memcpy worked; and guarantee that it never changes it's mind depending on any number of things.

The other alternative is to simply write the algorithm myself in C. This way I could guarantee copying from the base of the array instead of from the end. But, as you point out, memcpy is highly tuned for the machine architecture, and my "roll your own" isn't going to work as well.

Thanks a lot anyway. I really appreciate the thoughts. Maybe your idea will come in handy in some of my future projects. It was a really good idea.

David

After thinking a bit more about it, I realized the stuff about the GPF is probably not correct. It would just copy garbage.

As I think thru things, I try to document them so I (or someone else) won't come back later on and try to improve on the code without throughly thinking things thru. Based on your suggestion, I've added the following comments to my memoryFill() function.

void memoryFill( void* target, char* pattern, size_t ptrnlen, size_t numRepeats )
{  
   char* trgt = (char*)target;  //for ease in pointer manipulation.   
   ...
   //
   // If we KNEW that memcpy copied from the base of the src array to the base
   // of the target array, we could write an EXTREMELY fast algorithm:
   //    memcpy( trgt, pattern, ptrnlen );                     //put one copy at the base.
   //    memcpy( trgt+ptrnlen, trgt, ptrnlen*(numRepeats-1) ); //destructive copy the rest
   // Conversely, if we KNEW that memcpy copied from the end of the src array 
   // to the end of the target array, we could write:
   //    memcpy( trgt+ptrnlen*(numRepeats-1) , pattern, ptrnlen ); //put one copy at the end.
   //    memcpy( trgt, trgt+ptrnlen, ptrnlen*(numRepeats-1) );     //destructive copy the rest
   // However, the C standard distinctly says that memcpy can do it's copying
   // in whatever order it wants.  We CANNOT rely on any specific order.
   //
   ...
}

David

Hello,
is there any known algorithm to check how different are two files,
i mean to check how big is a difference between two files?

regards
termal