Algorithms

23-Dec-09 6:21

Lately I've been re-writing some graph algorithms to operate on adjacency-matrix graphs where the matrix is implemented as an array of ints/longs (for speed reasons)
Algorithms such as determining the size of a strongly connected sub-graph (somewhat like DFS, except the visiting order is different) and perfect graph coloring in chordal graphs.
They demonstrate uses of many bit hacks such as x &= (x - 1).

Would anyone like to see an article about this?
(and is this the right place to ask this question?)

Luc Pattyn23-Dec-09 7:00

23-Dec-09 7:00

harold aptroot wrote:
Would anyone like to see an article about this?
(and is this the right place to ask this question?)

yes, sure. and no (Article Writing, Lounge).

Smile | :)

Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles]

I only read code that is properly indented, and rendered in a non-proportional font; hint: use PRE tags in forum messages

harold aptroot23-Dec-09 7:13

23-Dec-09 7:13

Thanks Luc, next time I'll ask it in the Lounge Smile | :)

Tim Craig23-Dec-09 10:02

23-Dec-09 10:02

But he's asking if anyone wants an article about this particular algorithm. Not everyone wastes time in The Lounge. $Shucks | :-\$

You measure democracy by the freedom it gives its dissidents, not the freedom it gives its assimilated conformists.

harold aptroot24-Jan-10 6:44

Re: Speed comparison of data types [modified]

24-Jan-10 6:44

And how about the bitwise version of Algorithm X? Is that interesting enough?

harold aptroot21-Dec-09 5:30

Re: Speed comparison of data types

21-Dec-09 5:30

A float has only 24 bits that need to be divided, and one of them is "usually 1", so it requires less iterations than a full 32bit number (or even 64, which is a disaster)
Double's shouldn't really be faster than ints though (edit: ok yes it is possible in some cases, but it depends, see below), something else is going on here. Note that the time a division takes also depends on the magnitude of the result for ints, and on the roundness of the divisor for floats. This makes it harder to accurately compare the speed of integer division and floating point division.
As if that isn't bad enough yet there is also SSE vs good ol' FPU, and with Java you really have no clue which one you're getting, so I suggest you use C++ with assembly subroutines to take full control of what you're testing.

Hope this helps Smile | :)

edit2: forgot source, Agner Fog's optimization resources[^]

modified on Monday, December 21, 2009 11:36 AM

harold aptroot21-Dec-09 6:40

Re: Speed comparison of data types

21-Dec-09 6:40

Everything - ok maybe not, but pretty much.
Dividing two doubles may take as much as 21 cycles, and as little as 6. Dividing two 32bit ints may take 18 to 42 cycles, but it's usually on the smaller end of that. Whether it is on average better to divide doubles or ints depends on what kinds of values you have.
And doing any kind of math on denormals/NaN's/infinity's can incur a penalty.

Also, for 64bit numbers idiv is lower than div (up to 30%!)

Luc Pattyn21-Dec-09 6:37

Re: Speed comparison of data types

21-Dec-09 6:37

On most processors (the high-end of them at least) I have seen the speed for a series of numeric operations would be float >= double > int > long; there are several reasons for this:

1.
floating-point units are more highly pipelined, which results in a greater latency but a better throughput, so for a series of FP operations, the FPU would be faster than the same operations handled by integers.

2.
integer divisions compute only a few (say 3 or 4) bits per cycle, so long could take twice as long as int.
similar for real divisions, but more bits per cycle.

3.
float operations leave integer functional units available for other things, such as array indexing, iteration counting, etc. which are most always present in code too; as those units can operate in parallel, having more of them working for you should improve overall speed.

BTW: division (and square root) is inherently sequential, much more so than addition and multiplication.

Smile | :)

Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles]

I only read code that is properly indented, and rendered in a non-proportional font; hint: use PRE tags in forum messages

harold aptroot21-Dec-09 6:43

Fluid Layout By Custom Polygon Shapes

21-Dec-09 6:43

Floating point division is not particularly pipelined either though, the difference between the latency and the reciprocal throughput of FDIV is only 1 cycle (on a Core2)

Som Shekhar15-Dec-09 18:36

Som Shekhar

15-Dec-09 18:36

Like we have FlowLayoutPanel, where controls can automatically get laid out according to their sizes and sequence, I have a requirement of a fluid layout.

In a rectangle or area (say 500w X 100h), there are some fixed small controls. lets say a rectangle control of (100w X 30h) is fixed at point (0 top , 150 left) Now, I need to fill this bigger rectangle with small shaped controls with constant areas but variable widths. Height can be maximum wherever possible.

The controls not adjacent to fixed control will be rectangles So, no problems. The controls adjacent to fixed controls will need to take polygon shape of variable heights to fit in the balance space.

Any logic already existing? Any approaches?

And yes, this is for winforms.

What will be the height of fluid columns in a variable width cylinder

Som Shekhar15-Dec-09 7:26

Som Shekhar

15-Dec-09 7:26

Assume that there is a vertical cylinder with a diameters as follows

1cm at base
3cm at the height of 2cm
2cm at the height of 4cm
1cm at the height of 7cm
etc etc

Now, what would be the height of different colored fluid columns one over the other (Assuming there are no other forces). The columns are on top of each other and movable by drag and drop. Hence the calculation of each column depends on the bottom column.

Its not necessary to consider volumetric analysis because the solution could be in 2D for area also.

The function should take parameters of volume/area of each column at which it starts.

This is required for a graphical application where the movement of a liquid is shown in 2D.

I am looking for a faster alternative to "for" or "while" loops. It needs to be very fast so that a fluid motion could be achieved. Current algorithm is damn slow.

my current solution looks like:

while (volumeToAdjust &gt; 0)
{
    volumeCovered = Min (volumeToAdjust, volumePossibleInCurrentWidth)

    if(volumeCovered&gt;volumePossibleInCurrentWidth)
        height += heightForCurrentWidth
    else
        height += CalculateHeightForThisVolumeInCurrentWidth

    volumeToAdjust -= volumeCovered

}

This solution works fine for a single column of fluid. Multiple columns, multiple widths, the program slows down. Any better ideas?

Re: What will be the height of fluid columns in a variable width cylinder

Dr.Walt Fair, PE15-Dec-09 7:57

Dr.Walt Fair, PE

15-Dec-09 7:57

Do the diameters change or can they be hard coded?

What happens in between the values you gave? Is the diameter constant or tapered?

CQ de W5ALT

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

Re: What will be the height of fluid columns in a variable width cylinder

Som Shekhar15-Dec-09 8:05

Som Shekhar

15-Dec-09 8:05

Yes diameters can be changed. Also, the volume of each fluid column and their sequence can be changed by drag and drop. That is why the need of an algorithm to do it the fastest way.

Diameters are not tapered.

Prime Numbers List Website

Tadeusz Westawic14-Dec-09 5:31

Tadeusz Westawic

14-Dec-09 5:31

http://www.prime-numbers.org

Tadeusz Westawic

An ounce of Clever is worth a pound of Experience.

Re: Prime Numbers List Website

Luc Pattyn14-Dec-09 6:16

Re: Prime Numbers List Website

14-Dec-09 6:16

that list is not complete. Unsure | :~

Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles]

I only read code that is properly indented, and rendered in a non-proportional font; hint: use PRE tags in forum messages

Tadeusz Westawic14-Dec-09 14:44

Tadeusz Westawic

14-Dec-09 14:44

Of course it is, they all are.

Tadeusz Westawic

An ounce of Clever is worth a pound of Experience.

Re: Prime Numbers List Website

Tim Craig14-Dec-09 17:16

Sample code to encode/decode the plain text using ecc in C#

14-Dec-09 17:16

No it isn't, just the ones less than 10 billion. As far as anyone knows, the complete list is infinite. Roll eyes | :rolleyes:

You measure democracy by the freedom it gives its dissidents, not the freedom it gives its assimilated conformists.

udayanuk14-Dec-09 4:24

udayanuk

14-Dec-09 4:24

Hi every body ,
I am in critical position, can u plz tell me how the plain text to encrypt and decrypt using ecc(Elliptic Curve Cryptography) in C# i need step by step process if not the complete source code i need.
can any one help me plz......

advance thanks to for reply

Re: Sample code to encode/decode the plain text using ecc in C#

Luc Pattyn14-Dec-09 6:18

Re: Sample code to encode/decode the plain text using ecc in C#

14-Dec-09 6:18

I need someone to mow the lawn, paint the house and wash the car. plzzzzzzzzzzzzzzz

Hmmm | :|

Luc Pattyn [Forum Guidelines] [Why QA sucks] [My Articles]

I only read code that is properly indented, and rendered in a non-proportional font; hint: use PRE tags in forum messages

Tim Craig14-Dec-09 14:17

14-Dec-09 14:17

People here will help you with problems, not do your work or more likely homework for you.

You measure democracy by the freedom it gives its dissidents, not the freedom it gives its assimilated conformists.

Imaging Algorithm

Member 323506112-Dec-09 20:50

Member 3235061

12-Dec-09 20:50

i very need to an algorithm for Imaging of cars No in roads.
means how police cameras imaging of car No for forfeit.
because size of cars No is different.
thanx.

Re: Imaging Algorithm

Tim Craig13-Dec-09 17:43