Bignum timing - Algorithms Discussion Boards

Hi, I would be very glad if someone can help me with algorithm to solve following task.

We have a convoy of cars that are lined up in a row and must cross the bridge. Cars can´t overtake each other.
The bridge has limited capacity, which may not be exceeded.
Find the algorithm, which divides cars into groups so that the entire convoy cross the bridge in the shortest time.
Another group is allowed to enter only when the entire previous group cross the bridge.
Weight and speed of each car is known. The speed of group is determined by the slowest of car in the group.

Sample data:
Input
Output

Thank you for your help, Petr

I see some homework but I don't see a real question, except perhaps to do the homework.

I can´t find the algorithm to solve this thing, so I ask if someone can help me..
I thought about it, but I didn´t find the solution.

We don't have ready made algorithms for each problem. You could try and come up with your own; keep adding cars to the current group until you reach a threshold - be it number of cars or total weight, if either one is reached, send the group.

Then find the slowest car in that group; that's the speed of that group.

For the fastest way of the group, you'd try to move as much slow vehicles together as possible.

Bastard Programmer from Hell Suspicious | :suss:

If you can't read my code, try converting it here[^]

Member 11345380 wrote:
I can´t find the algorithm to solve this thing

However that looks exactly like what the homework is - to find the algorithm. Thus giving it to you would be doing the homework.

If you had an algorithm that you wanted others to review that would be a different matter.

hello guys. I'm newbies here since my friends promote to this forum.
can i know how to check 16 number of parity bits.
how to check the 16th parity bits?
Confused | :confused:

http://en.wikipedia.org/wiki/Hamming_code[^] ?

I am working on a bignum library and have been checking out some of the functions. I would like to know it the times I am seeing are good, bad, or indifferent.

To test big numbers, I used the RSA challenge file.

The times are in seconds and hundredths.
The initialize time is setting high priority and allocating all of virtual memory.
The read and split time is the time to read the file (one time) and tokenize it.
The edit time is for deleting unneeded lines in the file.

To get any difference in time between the different RSA instances, I had to loop 100,000 times to get different time values for the different instances (as you can see, the read/split time and the edit time are the default .01 second), thus those times are listed as 100K*xxx, i.e. "RSA-2048 100K*DTB conversion time: 2.06" means 20.6 microseconds for any single loop.

A single RSA instance includes the following data which is verified during the conversion (the first RSA instance is used as this example):

RSA-576

Status: Factored

Decimal Digits: 174

18819881292060796383869723946165043980716356337941
73827007633564229888597152346654853190606065047430
45317388011303396716199692321205734031879550656996
221305168759307650257059

Decimal Digit Sum: 785

The edit deletes the blank lines and the Status line. The initialize, read, and edit are only done one time.

The conversion time for each RSA instance includes validating that only decimal digits are present in the data, and that there the correct number of digits, and that the digit sum matches. I load the number as a radix 10 value and convert it to binary, and verify that the result has the correct number of bits. I save this binary value over the decimal digits so I can load it later without conversion. I also load this binary value to insure correct operation with radix 1. Each RSA instance is processed 100,000 times and then the time is calculated.

The SQRT times include loading the binary value and taking the SQRT and getting its remainder, and then squaring the SQRT and adding the remainder and comparing the result with the RSA instance value. Each RSA instance is processed 100,000 times and then the time is calculated.

With all of the above operations as described, are the times at all reasonable, i.e. 20.6 microseconds for DTB conversion and validation of a 2048 bit binary number and 63.6 microseconds to load and take the SQRT and validate (SQRT**2 + remainder == semi prime) for the 2048 bit binary value?

Dave.

Time to initialize:                       0.06

Time to read and split RSA.TXT:           0.01

Time to edit RSA.TXT:                     0.01

RSA-576  100K*DTB conversion time:        0.49
RSA-640  100K*DTB conversion time:        0.56
RSA-704  100K*DTB conversion time:        0.59
RSA-768  100K*DTB conversion time:        0.79
RSA-896  100K*DTB conversion time:        0.98
RSA-1024 100K*DTB conversion time:        1.13
RSA-1536 100K*DTB conversion time:        1.54
RSA-2048 100K*DTB conversion time:        2.06

Time to DTB convert 100K*RSA.TXT:         8.34

RSA-576  SQRT Time - 100k*RSA.TXT:        1.46
RSA-640  SQRT Time - 100k*RSA.TXT:        2.51
RSA-704  SQRT Time - 100k*RSA.TXT:        2.71
RSA-768  SQRT Time - 100k*RSA.TXT:        2.12
RSA-896  SQRT Time - 100k*RSA.TXT:        2.40
RSA-1024 SQRT Time - 100k*RSA.TXT:        2.80
RSA-1536 SQRT Time - 100k*RSA.TXT:        5.69
RSA-2048 SQRT Time - 100k*RSA.TXT:        6.36

You don't mean a big integer class?

http://msdn.microsoft.com/en-us/library/system.numerics.biginteger(v=vs.110).aspx[^]

PIEBALDconsult wrote:
You don't mean a big integer class?

No, I prefer to roll my own, only my functions process only positive integers. I do not use C++ or .NET, I am a MASM(5,6,7,8,9) programmer. OBTW, I read the class documentation but could not find a SQRT function, did I miss it somewhere?

If you are interested, I can email you the RSA.txt file (if you do not already have it) and you could implement and test the SQRT function and report the timings from the big integer class. My timings were taken on an HP Pavilion dv7-6c23cl - 6GB memory, quad AMD, 2.5GHz, 32 bit assembly, console application.

What I was looking for was anyone's WAG about how long the square roots of 576 bit to 2048 bit integers should take.

Dave.

I have several more questions to ask about bignumb processing, but since you were were the only one to respond to my original question I thought I'd just ask you directly via email, however your email seams to be blocked so I will ask here directly.

When you select the low limit for a potential P value of 40% of the decimal digit count, what would that be? Lets take a simple example - 40% of a 15 digit number would be 6 digits. My assumption is that it would be 100,000, 6 digits and the lowest number in 6 digits. If I wanted to insure that this was an odd number, would that change to 99,999 or to 999,999? 99,999 is not a 6 digit number, but 999,999 is certainly greater than the minimum 6 digit number of 100,000. Which should be used as the limit to match what RSA would generate for encryption?

To calculate this in binary, consider that 10^14 is 100,000,000,000,000 (15 digits) = 0x3,8D7E,A4C6,8000 (50 bits). 40% of 50 bits is 20 bits. The lowest 20 bit number is 0x8,0000 (the lowest number in 20 bits). If I wanted to insure that this was an odd number, would that change to 0x7,FFFF or 0xF,FFFF? 0x7,FFFF is just a 19 bit number, but 0xF,FFFF is certainly is certainly greater than the minimum 20 bit number of 0x8,0000.

The upper limit of 45% is easier to figure out. Just create the maximum number for that digit count (or bit count) and increment the count and create the
number as a base to a power, then decrement the result by 1 (it will always be odd, either 99999... or FFFFF...).

Dave.

It seems you know more about it than I do.

Thank you for the reply. I guess I'll just select the smallest low number to guarantee that I get most of the created keys. I already plan to check that low limit and if I find that that low limit value is above the solution value, I will just use it as a high limit and use the value 1 as thee low limit.

Dave.

hello all,
first of all escuse me for my English.

I am looking for help at the following problem:
at my final project for Bsc i get data and need to decide if a threshold had been crossed (tha data IS NOT BOOLEAN.. i get data about the velocity of an object)
the deffinition : if i get that for 1sec at least the given data is above threshold - It has been crossed.
it ofcourse complicated beacuse i need to filter "noise".

i thought to use "ALPHA FILTER" or "X/Y decision" or "Avarege" and other.. but i am sure that someone did a these on that and there is a proven algorythm to handle it.

thanks for all yours replies
sincerely yours,
sia

Need a lot more detail. What programming language? Where are you stuck exactly?

There are only 10 types of people in the world, those who understand binary and those who don't.

Hello everyone.
I'm looking for an algorithm to track the numbers at least duplicate content in a two-dimensional array to draw complex objects composed of rectangles, squares, triangles, hexagons, etc.

The constraints are:
- I require at least how many numbers should not be duplicated
- The vertices of the objects must contain at least duplicate numbers except those required
- Objects should be placed symmetrically

An example here:
example

In the example you can see duplicate values 0,10,15,18,19,25*,35,45,50 and the three individual numbers. * shared between two objects
The numbers 16,27,46 are the three numbers that I requested unduplicated

Course can be traced different combinations of objects that match the given condition.

They are looking for a fast algorithm. I have processing times biblical!

Thank you in advance

Looks like there is more than one problem.

I think you should give more details, like short data list with an explanation of how you deal with the problem (may be code snipset, or algorithm.)

Question: numbers are integers ? minimum and maximum values ?

Patrice

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

I have been working with C# using the FlickrNET API in order to create a slideshow that shows images from Flickr based on a single word search term.

This has been easy enough to implement thus far but the images shown on the slideshow are sometimes repetitive i.e. they show 10 of the same thing taken at a different angle by a single user.

As I am a bit of a newby to coding more generally I was looking for general advice or pointers on the best way to randomize these images according to their other related tags. So one way this might work is if someone searched "London" it could show everything with the tag "London" but use the other tags to organize the images so they are more diverse.

for example:
9 = 1001 in binary so the function GetNumOfBinary(9) = 2.
I know I can do it in o(n) (time) by convert it to binary and exam digit by digit.
I've been told I can do it using space as much as I need.

How can I do it? (it's seems impossible because I need to check every digit, doesn't matter which way I do it and it'll be still o(n))

Read this - http://en.wikipedia.org/wiki/Hamming_weight[^]

I'm not questioning your powers of observation; I'm merely remarking upon the paradox of asking a masked man who he is. (V)
תפסיק לספר לה' כמה הצרות שלך גדולות, תספר לצרות שלך כמה ה' גדול!

Thank you for the answer. This is the answer I was looking for.
Thank for the other for the answers.

There are several algorithms listed here[^]. For a 32-bit integer, you probably want "Counting bits set, in parallel[^]":

C#

int CountBitsSet(int v)
{
    v = v - ((v >> 1) & 0x55555555);                    // reuse input as temporary
    v = (v & 0x33333333) + ((v >> 2) & 0x33333333);     // temp
    return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}

Just don't ask me to explain how it works! Blush | :O

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

Richard Deeming wrote:
Just don't ask me to explain how it works!

How, how indeed...http://en.wikipedia.org/wiki/Hamming_weight[^]

I'm not questioning your powers of observation; I'm merely remarking upon the paradox of asking a masked man who he is. (V)
תפסיק לספר לה' כמה הצרות שלך גדולות, תספר לצרות שלך כמה ה' גדול!

It first sums pairs of adjacent bits, then it sums the groups of 2, then the same thing with the nibbles, and finally it cheats and sums the bytes with a multiplication.

if you're using c++ gcc - __builtin_popcount