PID control algorithms - Algorithms Discussion Boards

This looks interesting. It seems like it could be it. The only problem I can see with it is that it seems to be just for working with primes and semiprimes? Can I use this with any positive integer?

Thanks,
John

I really don't know. Sorry about that.

CQ de W5ALT

Walt Fair, Jr., P. E.
Comport Computing
Specializing in Technical Engineering Software

128 bits isn't "really big", so the asymptotically optimal algorithms aren't a very good choice here.
For 128 bits, I think what would work best is a simple multiword division. There's lots of stuff on google, it's in one of Knuth's books, and hackers delight has some code here[^] that also explains the algorithm.
edit: yes that does a division, and you go to mod from there - I know of no general way to do a mod without a division.

Just wondering, how did you implement multiplication? I hope it's not shifts and adds.. it works, to be fair, but it's very much slower than using long multiplication in base 2^32 (or base 2^64 if you have access to a 64x64->128 multiplication)

Hi,

i have created one portable application,initially it will take several time to install on to pendrive(installer doing more on dll copy option), for that i want to show time remaining in my UI.
can any one suggest me best algorithm to do this please

If you know how much data you need to install then you can set a timer to measure your install speed and use that value to estimate how much time the remainder will take. Adjust the value as you go through the install. Something like:
Total to install 1Mb
After installing 100Kb time taken is 2 seconds, so time left is ((1000 - 100) / 100 * 2) = 18 seconds
After installing 200Kb time taken is 3 seconds, so time left is ((1000 - 200 / 200 * 3) = 12
etc.

The best things in life are not things.

for this always we should know how much size is already installed/copied right...?

yogish293 wrote:
for this always we should know how much size is already installed/copied right...?

Yes, you can only ever make a reasonable estimate by knowing:
- How much has already been copied
- How much time the copying took
- How much data remains

The best things in life are not things.

I've been implementing a PID control algorithm[^] to control a heater (or cooler) to reach a setpoint. Everything works perfectly so far - PID really is magic.

Now the device I'm using can heat or cool depending on the polarity of the voltage you apply to it, so, with a suitable relay and some hardware, I can automate it to switch from heating to cooling or vice versa. As it currently works (I have a manual switch to reverse polarity), if you have a setpoint of, let's say, 30°C, it'll heat up, overshoot, shut off the voltage and cool naturally, then undershoot and turn the voltage back on. In theory, I suppose, it could be more efficient if, instead of letting it cool naturally, I switch the polarity and drive it back down. It's more aggressive and likely to be less stable perhaps, but my real concern is that it'll abuse the heck out of the relay which will be rapidly switching back and forth around the setpoint. So I was thinking that if I have some kind of "dead zone" area to add a "buffer" around the setpoint it might save the relay. In essence, the relay should only switch if you're a long way off and not when you are right around the setpoint. I was thinking if I made my input range say, -10 to +10 and in software I mapped it such that +10 gives the maximum voltage to the device and it reduces linearly until it reaches 0 at, let's say +2. Then from +2 to -2 the voltage remains at zero, and from -2 to -10 the voltage goes up again, but the polarity is reversed.

One concern here is that in addition to stopping it switching polarity, it'll also delay turning it back on. Also, depending on where the setpoint is, I should be spending most of the time either cooling or heating. For example, if I change the setpoint from 10°C to 5°C, I should spend most of my time cooling, I really shouldn't need to heat at all unless I drastically overshoot, and I'm not sure whether this will automatically pick up on that.

Does this sound like something that might work (I'm waiting on the hardware at the moment, so I'm just thinking it through right now)? Is there a way to handle this kind of setup? Is it just a bad idea? Should I just not try and drive it so aggressively?

Any hardware control experts out there?

It's normal practice in controls to use hysteresis around a set point to prevent overworking the hardware. Even air conditioning systems use it. If you set a target of 70°F, for instance, the heating unit won't kick on until the temp drops to about 68, and won't shut down until it senses 71 - 72. This prevents constant cycling on and off, which is very important if there's a motor involved. They tend to overheat, and can be damaged by rapid cycling.

Don't try to set it to aggressively, else you might fall into a positive feedback situation, with the controlled value oscillating around, but never actually stabilizing at the setpoint. That will ead to rapid equipment failure.

You're on the right track... carry on! Big Grin | :-D

Will Rogers never met me.

Thanks for the sanity check. Hopefully I'll get the hardware piece I need tomorrow and can start playing around.

Do not look so much into code - a good setup of the "hard ware" is more important.
Find a good distance for the thermometer from the heater/cooler proper. Mix the item to be heated/cooled well; if you cannot mix the items proper, mix the surrounding media (air or liquid) and do not forget that the delay will be bigger.

As already suggested, using histeresys is a good, proven technique.
For your control system, you may have a look at fuzzy logic too.

If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
-- Alfonso the Wise, 13th Century King of Castile.

This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong.
-- Iain Clarke

[My articles]

Hello,

What algorithm does one use to find an empty entry on a 3x3 grid?

Suppose you have a checkers board where 8 of the 9 squares are occupied with a checker piece.
How do you determine the one empty spot that is left?

Thank you

In the absence of any further logical constraints (i.e. emptiness of each cell is independent of other cells), brute force (checking all the cells until you find an empty one) is the only way. (On a 3×3 grid that is no problem.)

It depends. What data structure is your grid made of? Is it a bit board?

My Grid is a Xaml Grid (Silverlight). Its internal structure is like this:

<Grid
xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
Loaded="onLoaded" ShowGridLines="True" Background="CornflowerBlue">

<Grid.ColumnDefinitions>
<ColumnDefinition Width="100"/>
<ColumnDefinition Width="100"/>
<ColumnDefinition Width="100"/>
<ColumnDefinition/>
</Grid.ColumnDefinitions>

<Grid.RowDefinitions>
<RowDefinition Height="100"/>
<RowDefinition Height="100"/>
<RowDefinition Height="100"/>
</Grid.RowDefinitions>

<Border Grid.Row="0" Grid.Column="0" x:Name="b1" MouseLeftButtonUp="switchPlaces" >
<Canvas x:Name="canvas1">
<Ellipse Width="100" Height="100" x:Name="ellipse1" Fill="Red" Visibility="Visible"/>
</Canvas>
</Border>

/* repeat 8 times */

Brute force it is then.
I hope you're not planning to make a big grid out of this, because it's going to be terribly slow..

I have been trying to bruteforce it all day but I can't manage to do so. I work with Javascript.

See code:

function switchPlaces(sender) {
for (var i = 0; i < borderArray.length; i++) {
var oldLocationChild = sender;
var oldLocationParent = gamePage.content.findName('canvas' + (i+1));

if (oldLocationParent.children.count == 0) {
//alert("no item");
var emptySpot = borderArray[i];
sender['Grid.Row'] = emptySpot['Grid.Row'];
sender['Grid.Column'] = emptySpot['Grid.Column'];
oldLocationParent.children.remove(oldLocationChild);
}
}
}

/** .remove works
sender row and column works

emptySpot does not work. For some reason, this function only works when I hardcode remove an Element from its Canvas. Then there is only one Canvas of the 9 that has no Element and the code picks it up.

This is not what I need. However, I can't seem to dynamically get the empty cell in Javascript.. it always looks at the hardcoded Xaml. I have no idea how to do this anymore. I'm lost.

I have absolutely no idea. I don't know anything about javascript or xaml. The problem you're having doesn't really appear to be algorithmic in nature - perhaps you should try the Web Development forum?

Funny. The Web Development forum pointed me towards here. I'll try though.

Trying to make sense of what you have in this thread. It looks like you are now trying to change the Grid.Row and Grid.Column of the border control. This is fine. But you also need to move the empty border as well as moving the "sender". Otherwise it's not a swap.
So if you need something like this (I haven't done JS in a while, so consider this semi-pseudocode):

var tempRow = sender['Grid.Row']
var tempCol = sender['Grid.Column']
sender['Grid.Row'] = emptySpot['Grid.Row']
sender['Grid.Column'] = emptySpot['Grid.Column']
emptySpot['Grid.Row'] = tempRow
emptySpot['Grid.Column'] = tempCol

I don't understand why you are trying to remove anything. I think this should work.

A minor performance improvement would be to exit your for loop after you find the empty cell. You know there is only one, so why keep looking after you found it?

A major performance improvement would be to keep track of where the empty cell is, even if you didn't keep track of it when you populated your grid (which would be even better). Once you've found it the first time, you should be able to keep track of it from there on out and never have to search for it again.

Hi,

I would like the following functionality:
- None of the Ellipse elements may be at the same Grid.Row|Grid.Column combination as another Ellipse in the ellipseArray.
- Each Ellipse has to find its unique position on the Grid [x,y].
So I can't have two Ellipses both having the same value for <Border Grid.Row and Grid.Column> (e.g. both ["0","0"]).

See code here:
<Border Grid.Row="0" Grid.Column="0">
<Canvas>
<Ellipse Width="100" Height="100" Fill="Red"/>
</Canvas>
</Border>
..(This code is repeated 9 times, where .Row and .Column are variable. The last <Border> has no <Ellipse>)I have 8 Ellipse elements on a Grid of 9 squares.

It looks sort of like a collision algorithm.
How would I accomplish this?

----

EDIT: I fixed it. See code below.

function checkPositions() {

var j = 0;
var collision;

do {
var newRow = Math.floor(Math.random() * 3 + '');
var newCol = Math.floor(Math.random() * 3 + '');
borderArray[j]['Grid.Row'] = newRow;
borderArray[j]['Grid.Column'] = newCol;

collision = false;
for (var i = 0; i < j; i++) {

if (borderArray[i]['Grid.Row'] == (borderArray[j]['Grid.Row'])
&& borderArray[i]['Grid.Column'] == (borderArray[j]['Grid.Column'])) {
collision = true;
break;
}
}

if (!collision) {
j += 1;
}

} while (j < randomRowsArray.length+1);

modified on Saturday, July 16, 2011 11:53 AM

What you did is fine for a 3x3 grid. But a more efficient way would be to produce a list of all the possible pairs of points and then randomly pull a pair from that list, assign it to your item and then remove it from the list. This way you can guarantee no collisions. As a bonus, whatever you have left in the list at the end is all your empty cells.

Whether this method is faster than yours depends on the size of the grid and the number of items in the grid. For example, in a 10 x 10 grid with 99 items, it will almost certainly be faster. In a 10 x 10 grid with 1 item, it certainly isn't.

However, the worst case performance of your algorithm is infinity!

modified on Thursday, July 21, 2011 3:45 PM

Hello,

I have a grid with 9 cells, where each cell has a [row,col].

Please see the following image for my problem description:
problem situation

I would like to have the following functionality:

- When you click on one of the circles in the grid,
the clicked circle takes in the place of the only empty square on the grid.
The empty space then in turn switches places with the circle that has just been moved.

Seems easy enough, but I can't figure out how to do this.

My new code is this:

    for (var i = 0; i < borderArray.length; i++) {<br />
        if (borderArray[i].findName('ellipse' + (i + 1)) == null) {<br />
            alert('sr: '+ sender['Grid.Row']);<br />
            alert('sc: ' + sender['Grid.Column']);<br />
            alert('br: ' + borderArray[i]['Grid.Row']);<br />
            alert('bc: ' +  borderArray[i]['Grid.Column']);<br />
<br />
            sender['Grid.Row'] = borderArray[i]['Grid.Row'];<br />
            sender['Grid.Column'] = borderArray[i]['Grid.Column'];<br />
        }<br />
    }

sender[row,col] keeps being 0,0 for some reason, no matter which circle I click on.
It should take the [row,col] value of the sender I clicked. This is strange.
//Edit: fixed this partially. The 'MouseLeftButtonUp' should have been on <border> not on <ellipse>

Languages used:

- JavaScript
- Silverlight

Thank you

modified on Friday, July 15, 2011 1:03 PM

I think your problem is a XAML/JS problem not an algorithm problem. I assume borderArray is a flat array of all 9 cells and you are looking at each one in turn to find the one that is empty. That is a perfectly valid way of doing it, although a better way would be if you have populated the grid in the first place, can't you just keep track of which cell is empty instead of searching every time? That would be much more efficient.

As to what causes your actual problem, I can see a couple of things that strike me as odd, but you don't provide enough information to make sense of it.

Firstly, if every cell in your grid contains a border (which I assume is what borderArray is), setting another control to the same grid row and column does not make it a child of the Border (assuming your sender is the ellipse and not the border itself) in that cell.

Second, your search for 'ellipse' + (i+1); I'm assuming you have 8 ellipses that you've named ellipse1, ellipse2, ellipse3, etc. Then you've put ellipse1 in cell 0,0 ellipse2 in cell 0,1, etc. Now, once you've swapped one of those ellipses to a different cell, your borders (which I'm assuming aren't moving) don't hold the same ellipse (although they don't hold them at all, as I said earlier) as they started with. So looking for ellipse1 in borderArray[0] isn't valid if borderArray[0] now contains ellipse2.

Finally, if, as I suspect, you set this up so that the ellipse originally are children of Border controls that are actually in the grid, then it's not a surprise that you get Grid.Row and Grid.Column of 0,0. The ellipses aren't actually in the grid, their parents are.