|
I've thought about this problem (while waiting for elevators!).
A few random comments: The standard algorithms used by existing elevators seem to be non-optimal; A cluster of floors where an elevator has been requested will slow down multiple elevators making everyone wait unnecessarily. This is because when the first elevator stops at the first floor in the cluster, the remaining elevators will get bogged down by the next floors in the cluster.
It would be more optimal for a single elevator to handle the cluster, while the others continue down with no delays.
It's hard to optimize for the number of people, because there's no way of knowing exactly how many people are on a particular elevator. We can make a guess, however. When an elevator stops at a requested floor, we can assume at least one person got on. But we don't know how many got off.
Using artificial intelligence may optimize the algorithm better than any "blind" approach, that doesn't take historical use patterns into account.
"Microsoft -- Adding unnecessary complexity to your work since 1987!"
|
|
|
|
|
Hi Alan, thanks for responding. I've been exceptionally busy and thrown off-track by some hardware problems in the last week, so have not kept up with this thread.
I think about that's a good point about using some for of of AI technique, or even some form statistical analysis (factor analysis).
If you had a three month data set of all the kinds of data I described above, it would seem you could factor-out use patterns: such as heavy traffic from all upper floors, or any floors above coffee-shop level, or ground-floors, or check-out floor, down, in the AM hours, etc.
Near check-in time you'd expect ground-floor to check-in floor (if separate) to be heavy, followed by lots of traffic of people going up to their rooms, and so forth.
Similarly, hotels often have special events at noon, or in the evening involving large numbers of people; it's easy to anticipate when heavy elevator-use periods related to those events may be ?
And, I wonder if the kind of "fuzzy" algorithms developed by Japanese device makers might be useful here ?
I wonder how long it will be before elevator makers put small video-cams with a wide-angle lens on each elevator, and from the pictures being fed back into a central dispatching system compouter, roughly estimate the size of the crowd waiting on a particular floor ? Maybe it's already being done ?
best, Bill
<color>"When it comes to atoms, language can be used only as in poetry. The poet, too, is not nearly so concerned with describing facts as with creating images." Niels Bohr
|
|
|
|
|
Hello,
I'm a complete newbie to the field of cryptographic algorithms themselves, always having relied on third-party libraries and code in the past. Now I'm starting to poke around with them by myself I finally managed to throw together some sort of tiny cryptographic library in VB.NET. However, I'm concerned that... quite frankly... it's a bit rubbish. Sorry about the long code block here:
Imports System.Numerics
Public Class BlumBlumShub
Private _x As BigInteger
Private _p As BigInteger
Private _q As BigInteger
Private _m As BigInteger
Private _pow As New BigInteger(2)
Public Function NextNumber() As BigInteger
_x = BigInteger.ModPow(_x, _pow, _m)
Return _x
End Function
Public Sub New(ByVal seed As BigInteger)
_p = BigInteger.Parse("32416190071")
_q = BigInteger.Parse("32416185031")
_x = seed
_m = BigInteger.Multiply(_p, _q)
End Sub
End Class
Public Class RandomBitStream
Private _b As BlumBlumShub
Public Function ReadByte() As Byte
Dim num As Byte = 0
For i = 1 To 8
num += Math.Pow(i, 2) * If(_b.NextNumber().IsEven, 1, 0)
Next
Return num
End Function
Public Sub New(ByVal seed As BigInteger)
_b = New BlumBlumShub(seed)
End Sub
End Class
Public Class BlumXor
Private _bitSrc As RandomBitStream
Private _key As BigInteger
Public Sub Cipher(ByRef message As Byte())
_bitSrc = New RandomBitStream(_key)
For i = 0 To message.Length - 1
message(i) = _bitSrc.ReadByte() Xor message(i)
Next
End Sub
Public Function ByteToStr(ByVal inByte As Byte) As String
Return inByte.ToString().PadLeft(3, "0")
End Function
Public Sub New(ByVal keyStr As String)
Dim encoder As New System.Text.ASCIIEncoding()
Dim keyBytes As Byte() = encoder.GetBytes(keyStr)
_key = BigInteger.Parse(String.Join("", Array.ConvertAll(Of Byte, String)(keyBytes, New System.Converter(Of Byte, String)(AddressOf ByteToStr))))
End Sub
End Class
And that is that. Firstly, I think my implementation of the BlumBlumShub PRNG is off, secondly I'm not entirely sure that I should be using the parity of numbers generated to give me random bits and thirdly I'm not so sure about my use of Xor or how I'm generating a seed integer for the PRNG from a string. I welcome the input and criticism of any cryptographers or mathematicians out there, plus anyone else that can see problems with my code.
SixOfTheClock
A programming language is to a programmer what a fine hat is to one who is fond of fancy garden parties. Just don't try wearing any .NET language on your head. Some of them are sharp.
modified 14-Sep-12 6:30am.
|
|
|
|
|
Hi all,
I am trying to write a windows forms program to communicate to a CNC-machine from the 1980ties.
The machine uses a 6802 microprocessor and communicates with a Desktop computer with a DOS program.
The communication is in ASCII characters and is in the following format:
4 spaces and a 3 digit value and a checksum character or 3 spaces and 4 digits and a checksum character.
So a total of 7 characters and a checksum character.
This is a part of the original message(space represented as | and checksum character bold):
||||853>|||1370%||||248>|||1204'||||||00||||||11||||7887||||2156||||2552|||2346#|||2346#|||1031#
I already tried some things like adding all decimal ASCII values and MOD against all possible values,
like ||||853 : 32+32+32+32+56+53+51 MOD some value and add 30 or 31 to make sure result is in the range of printable characters,but no luck.
note that 853 and 248 have the same checksum, also 2346 and 1031.
I hope someone recognizes the checksum algorithm or can help me to find out how the checksum character is calculated.
Thanks,
Groover
0200 A9 23
0202 8D 01 80
0205 00
modified 9-Sep-12 16:14pm.
|
|
|
|
|
Easy,
XOR the 7 ascii values together.
" 853>"
32^32^32^32^56^53^51 = 62 ">"
" 248>"
32^32^32^32^50^52^56 = 62 ">"
" 2346#"
32^32^32^50^51^52^54 = 35 "#"
" 1031#"
32^32^32^49^48^51^49 = 35 "#"
" 1370%"
32^32^32^49^51^55^48 = 37 "%"
" 1024'"
32^32^32^49^48^50^52 = 39 "'"
" 00"
32^32^32^32^32^32^48 = 48 "0"
" 11"
32^32^32^32^32^32^49 = 49 "1"
" 7887"
32^32^32^32^55^56^56 = 55 "7"
" 2156"
32^32^32^32^50^49^53 = 54 "6"
" 2552"
32^32^32^32^50^53^53 = 50 "2"
Alan.
|
|
|
|
|
Thank you Alan,
I wrote a function in my program and it works perfect.
Groover,
0200 A9 23
0202 8D 01 80
0205 00
|
|
|
|
|
I have a group of points that I need to plot on a graph and calculate the line of best fit(Slope and Intercept) in a programming language.
for example
x 0 1 2 3 4
y 40 41 45 41 47
At the moment I am using and have implemented the Least Squares algorithm
here http://en.wikipedia.org/wiki/Least_squares[^]
I was wondering whether anyone knows of a computationally more efficient algorithm with close to the same accuracy and be able to explain how the algorithm works?
Thanks in advance
|
|
|
|
|
A decent implementation of linear fitting by LSQ should run in O(n) time and O(1) space.
One pass over the data, accumulating sum(x), sum(y), sum(x*x) and sum(x*y) then crunch those four (and n) to get the answer.
If you're just doing a simple linear fit, DON'T get sucked into all the matrix stuff. Waaaaay overkill.
Cheers,
Peter
[edit]forgot sum(y)[/edit]
Software rusts. Simon Stephenson, ca 1994. So does this signature. me, 2012
modified 5-Sep-12 2:43am.
|
|
|
|
|
So, a quick maths check.
If I want to store the results of an iterative algorithm for every pixel in an image (fractals!) then I think it's a dumb thing to start with but want to check before I even start bothering to write the class that would store the results.
Assume image size is 1000 x 1000, so 1 million pixels
Algorithm is an iteration of Zn+1 = Zn^2 + Z0 up to a maximum of say 10,000 times
Each iteration results in a complex number
A complex number is a structure with 2 doubles (let's assume it occupies 128 bits for simplicty)
Theoretically this could result in 10,000 x 1,000,000 complex number instances
This is 1 x 10^10 instances, at 128 bits each that 1.28 x 10^12 bits
Which is:
1.6 x 10^11 bytes
1.56 x 10^8 K bytes
152,588 M bytes
149 G bytes
That would seem a dumb thing to do
But I'm assuming that my maths is correct and there aren't memory optimisations I know nothing about.
Mike
|
|
|
|
|
Does your algorithm depend on the pixel colour or pixel position?
What I'm thinking is that, if it depends on your pixel colour alone, then your iterations for two pixels with identical colour should yield the same results. If you come up with a way of storing the results in bulk for pixels with the same colours, then your memory consumption would most likely go way down.
Other than that, after a quick at your numbers as displayed above, they seem to be correct
Full-fledged Java/.NET lover, full-fledged PHP hater.
Full-fledged Google/Microsoft lover, full-fledged Apple hater.
Full-fledged Skype lover, full-fledged YM hater.
modified 3-Sep-12 15:22pm.
|
|
|
|
|
Pixel position, it's converted to a complex number which is then stuffed into the iterative equation and that results in a long (or short) list of complex numbers, Z0 to Zn, n could be anywhere from 0 to the limiting number - 10k in the example I gave, but could be much much lower (50) or much much higher.
The problem arises since the way I'm going through this 'rite of passage' (doing Mandelbrot images) is to try and create a pluggable set of classes that could be used to implement any fractal set (mandelbrot, julia, newton etc.) and use any of the many colourising methods (escape time, distance estimators etc.). Adding a new set (e.g. Burning Ship, Phoenix) or a new colourising method (e.g. escape angle) therefore simply entails creating a new class that does that specific job and implements the relevant interface.
The consequence of this is that the key class which manages and calls the FractalSet iterators and then calls the colouriser to get a colour for the complex number (pixel) under investigation has no way of knowing what data that colouriser needs, the classic escape time needs only the actual number of iterations, the distance estimators need things like the last 2 (or more) results of the iteration.
So the above question came from my first idea which was to store them all whilst the entire image was iterated pixel by pixel - bad idea!
I think my way of doing this will be to change the colouriser interface and have a method that takes the complete result set of results for a single iteration, processes it as appropriate (turning potentially thousands of complex numbers into something much smaller) and builds the data set it needs, plus a method to to manipulate them once all iterations have been completed and finally a method that spits out the image.
Thanks for the confirmation.
Mike
|
|
|
|
|
Mike-MadBadger wrote: I think my way of doing this will be to change the colouriser interface and have a method that takes the complete result set of results for a single iteration, processes it as appropriate and builds the data set it needs
Yeah, if you can do that (I thought storing all the values was a requirement or spec or mandatory), it definitely beats having to store tons of values.
Now, in terms of speed, I have no idea what the gain would be, but I'm also betting it would be faster than storing the calculations (which, come to think of it, in your particular case would only be a cache of some sort).
Mike-MadBadger wrote: Thanks for the confirmation.
I doubt I was of much help, but you're welcome
Full-fledged Java/.NET lover, full-fledged PHP hater.
Full-fledged Google/Microsoft lover, full-fledged Apple hater.
Full-fledged Skype lover, full-fledged YM hater.
|
|
|
|
|
Andrei Straut wrote: I thought storing all the values was a requirement or spec or mandatory
The closest I have to a spec. is the jumbled nonsense in my head and its many and frequent lurches from bad to poor design (an improvement of sorts!).
Thanks again.
Mike
|
|
|
|
|
Even if you wanted the results of all iterations, why would you need the results of all iterations for all pixels at the same time? Surely the pixels are independent?
|
|
|
|
|
Absolutely correct, I don't need them all at the same time.
That was my gut reaction to the problem of using pluggable colourisers, i.e. the Imager class, that does the looping through the pixels, asks a FractalSet to iterate its equation and send back the results, it would then manipulate them and finally send the manipuplated data to the colouriser. However, the Imager doesn't know what data the colouriser needs, it could be as simple as the iteraton count and the max iterations, it could be the average of all iterations, the escape angle etc.
The conclusion is that I need to send the results of each iteration to the colouriser immediately after each iteration has finished. The colouriser can then do whatever manipulations it wants to and store only the data it needs rather than the Imager storing everything and only invoking the colouriser once all iterations have finished.
I think that'll work, we'll soon see...
Mike
|
|
|
|
|
Noooo
This question is on the news page. Really! Must be a slow news day.
Ah well, my dumb question for the world to peruse and giggle quietly to itself.
|
|
|
|
|
What use could it be to keep all iterates for all pixels ? The main reason I can think of is to render an animation showing the evolution of convergence, and be able to play it forwards but also backwards. (If only forwards, your machine will be fast enough to recompute the iterates on the fly; if just the final result matters, there is no reason to stroe all iterates.)
If your purpose is that kind of animation, a solution can be to MPEG compress the rendered images, achieving decent storage amounts even for large frame numbers.
|
|
|
|
|
See my answer to harold atropot, hopefully that answers your question - essentially I don't need to store them all, that was just a really poor way of solving a problem (so poor it wouldn't have worked).
Creating animations is a much later (if ever) addition to this project, right now it's just about me learning how to use interfaces, design patterns etc.
Thanks,
Mike
|
|
|
|
|
Mike,
Do you need to keep all 10,000 iterations leading up to your final image? I thought the idea with fractals was to loop back through the formula until you either settle on a value of not, and then paint the pixel (or not). Wouldn't you just need the final iteration, or maybe an array with your decision (paint/don't paint) for each pixel? Would reduce the size of your data by 10k.
Paul
|
|
|
|
|
The colouriser needs all the iterations for a given pixel (= a complex) since there are n ways to colourise a fractal, some of which manipulate all the values of Zn achieved during an iterative cycle.
However, the colouriser doesn't need all iterations for all pixels at the same time, so I am now sending all iterations for one pixel to the colouriser, it can then do whatever it needs, store its necessary data (number of iterations, escape angle, whatever) and then the cycle starts again for the next pixel. I think this is quite close to your suggestion?
Mostly the colourisers store their data in List(Of T) objects since they can cope better than arrays with changing dimensions.
Mike
|
|
|
|
|
Mike-MadBadger wrote: I am now sending all iterations for one pixel to the colouriser, it can then do whatever it needs, store its necessary data (number of iterations, escape angle, whatever) and then the cycle starts again for the next pixel. I think this is quite close to your suggestion?
Yes, I was thinking in terms of storing only what is absolutely necessary for each pixel.
Good luck.
Paul
|
|
|
|
|
You may want to check out www.FractalForums.com.
The people that wrote mandelbulb (mandelbox?) hang out there and may be a source of programming knowhow.
I'm user panzerboy there, I've written a few plugins for FractalExtreme. I use that to make zoom movies which I post on YouTube as CommandLineCowboy.
FractalExtreme is somewhat limited in its colouring, its strictly iteration count indexing into a 228 element palette table. I often do multiple renders with different palettes and mappings layering the results. If you check out my latest videos you'll see that you can still accomplish quite a lot with simple iteration count colouring.
Your 'average of all iterations' comment intrigues me. In Fractal Extreme you can hold Shift and Ctrl and click on the initial mandelbrot set to see the 'iteration paths'. Values in the M-set spiral inwards around a central point which would be your average value. The values outside the set with high iteration counts buzz around a point before going outside the window. Again that average would the central point only slightly altered by the last few iterations. So I'm thinking you may not need all the iterations to find the axis of the spirals.
|
|
|
|
|
Jeremy David Thomson wrote: Your 'average of all iterations' comment intrigues me
Then I was probably a little misleading, I was just trying to pick an example as to why you might want anything other than than the classic 'IterationCount / MaxIterations' which is what most folk doing this 'rite of passage' project would recognise. More practical examples might have been standard deviation or other more complex statistical analysis - many (all?) of which have been done by someone at some point to varying degrees of success and aesthetic value.
Jeremy David Thomson wrote: You may want to check out www.FractalForums.com
That I have discovered, though I have only scratched the surface at this point. It seems one of the better (or at least more broad ranging) places to go, though there are literally millions of places to get little bits and pieces of useful information.
Thanks for your time.
|
|
|
|
|
Howdy
Hmm, is double precision complex really needed, in your case e.q. storing all in int's could
reduce required space 4x.
also maybe the whole image could be 7zipped.
You could allocate each time 1M ints array and run 7zip through it, I assume a lot of compression could be achieved that way
Dunno though
|
|
|
|
|
Zipping wouldn't work due to the very nature of fractals: they're all about chaos and unpredictability, whereas compression algorithms are all about detecting patterns and predictability of data sequences. The two don't mesh. Ever.
P.S: for the same reason restricting yourself to lower precision won't work either. In fact, with a precision of only about 55 bit (which I think is the usual length of the mantisse in a double), doing more than about 500 iterations will yield no meaningful data. It may still look nice when visualized (which is usually the point of fractal programs), but you are effectively looking at rounding errors. I would go so far as to say you need an arbitrary math library for more than 100 iterations.
|
|
|
|
|