For those new to message boards please try to follow a few simple rules when posting your question.
Choose the correct forum for your message. Posting a VB.NET question in the C++ forum will end in tears.
Be specific! Don't ask "can someone send me the code to create an application that does 'X'. Pinpoint exactly what it is you need help with.
Keep the subject line brief, but descriptive. eg "File Serialization problem"
Keep the question as brief as possible. If you have to include code, include the smallest snippet of code you can.
Be careful when including code that you haven't made a typo. Typing mistakes can become the focal point instead of the actual question you asked.
Do not remove or empty a message if others have replied. Keep the thread intact and available for others to search and read. If your problem was answered then edit your message and add "[Solved]" to the subject line of the original post, and cast an approval vote to the one or several answers that really helped you.
If you are posting source code with your question, place it inside <pre></pre> tags. We advise you also check the "Encode "<" (and other HTML) characters when pasting" checkbox before pasting anything inside the PRE block, and make sure "Use HTML in this post" check box is checked.
Be courteous and DON'T SHOUT. Everyone here helps because they enjoy helping others, not because it's their job.
Please do not post links to your question into an unrelated forum such as the lounge. It will be deleted. Likewise, do not post the same question in more than one forum.
Do not be abusive, offensive, inappropriate or harass anyone on the boards. Doing so will get you kicked off and banned. Play nice.
If you have a school or university assignment, assume that your teacher or lecturer is also reading these forums.
No advertising or soliciting.
We reserve the right to move your posts to a more appropriate forum or to delete anything deemed inappropriate or illegal.
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):
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?
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
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.
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.
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
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!
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.
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))
It depends on your abstract model. With the usual model, you can't do any better than O(n) (so o(n) is not happening, or did you write a lower case o by accident?) - obviously on a plain old Turing machine, you're going to have to read every bit.
But this problem is in NC. You could sum n/2 pairs of bits, then n/4 pairs of "2bit numbers", n/8 pairs of nibbles, etc, and you're done in log n steps, with each step taking logarithmic time too (adders) (sometimes not counted), all with a polynomial number of processing elements.
Similarly in "broadword computing", you would say that you could compute this in O(log n) broadword steps - using the same construction, but now every layer is a couple of steps (mask and add) (with the addition counted as 1 step, instead of as a circuit of depth O(log n))
Practically, on 32bit words but "pretending 32 is not a constant", you can still use the same construction for an O(log n) algorithm possibly with a multiplication trick to do several sums at once (already shown in answers) or lookup tables or (with as much space as you need, you could cheat terribly and compute any mapping from 32bit integers to anything in a single step), if available, the popcnt instruction.
For arrays you could use a pshufb-based trick[^] (pshufb is awesome).
This is nothing to do with Python, or any other language. It's a simple matter of sorting the intial values into order and then searching for the two points closest to the one entered by the user. Could be speeded up by binary chop (Google for that).
I think Richard was suggesting that you google "Binary chop" not sorting.
Try a search of "python binary search closest value" - the first hit that came up for me (in Google) was an answer to the same homework question