|
Having an infinite amount of stuff like that doesn't really make sense. Unlimited perhaps, in the sense that there is no a-priori constant limit that you can abuse to make all algorithms collapse to constant time. But infinite, no way. Even if it's sorted, it could start with infinite zeroes, which you therefore cannot count, nor could any higher element ever be reached. It just doesn't work.
|
|
|
|
|
Pi goes to inifinite decimal places .. creating the infinite output is easy and such things exist. Any irrational number is an example, the element involved being a digit.
Even in your case a computer will get thru thousands or millions of compares for a single digit per second.
If I asked you to count the digit 7 occurance in the PI output you can easily do it, and you could carry the count until you ran out of memory, disk space etc to hold the count. You only need the count you don't have to store the thing.
Doing it in O (log n) that is the question?
In vino veritas
modified 28-Oct-17 13:12pm.
|
|
|
|
|
Describing a procedure that produces infinite output is easy, yes. But you can never have all of its output, and no you cannot count the number of occurrences of the digit 7 in the decimal representation of PI. You can start to count, but you would never have the answer. That would technically not even be an algorithm, because an algorithm is an Effective Method, which means it must terminate in a finite number of steps.
|
|
|
|
|
I can't and wont agree, you can terminate any infinite processes on a different criteria
Pi to the 100,000 place is a classic example as is counting.
So even infinite processes can terminate in a finite number of steps you just don't
get a full precision solution.
Rounding, image analysis, smoothing, infinite searches and a pile of other fields all
have solution infinite algorithms that if left run would never end. However you concluded
them when you have sufficient accuracy for your needs and they are most definitely
normally called algorithms. I even know several of them are patented as Algorithms even
though under your definition they aren't because they would never end, except for they
pick an point to terminate the processing.
As a bit of humor I am not sure the field of Fractals knows it can't have algorithms
because every calc in the field goes to infinity you have to force bailout 
Given there are multiple definitions of Algorithm I will leave it up to the OP to work
out with his teacher what definition of Algorithm they want to use. I am quite happy to
call what they are doing an algorithm even if you are not and it will just become a pointless
argument.
In vino veritas
modified 29-Oct-17 5:41am.
|
|
|
|
|
If you have it terminate, it's simply not infinite anymore.
|
|
|
|
|
You are trying to duck the problem some algorithms go on to infinity.
Some fractals never terminate they are designed to spit differences, they run until you turn them off they
are in every sense of the word infinite. You could also add machine learning AI, it never stops learning.
It does stuff in between time, termination is not a requirement of getting usable output.
At no point in either of these concepts do I need to specify a termination or need finite things.
You could claim they might run out of resources but that is also the case to the question as posed by the OP.
You are just applying a physical world restriction to bring in a terminate. However it's an algorithm long
before it ever terminated and as a concept it does run forever it would never end of it's own choice.
To me you are adding significance to infinity/finite which are just concepts. Abnormal or selected terminations
are just a byproduct of the real world, to the algorithm they can be meaningless.
I doubt we will agree on this stuff we are sort of differing around physical vs concept infinity.
You are wanting to take a much harder literal approach than I would in programming an algorithm.
All that ends up happening is things I will call an Algorithm you won't call that, you would call
it something else a process, a system or the like.
In vino veritas
modified 29-Oct-17 14:14pm.
|
|
|
|
|
I'm not bringing in any real world things. The definition of an algorithm says that it must terminate - that's not just something random I'm throwing in. That's just some distracting naming though.. infinite processes then, sure. And we could define an infinite process that starts to count the occurrences of a specific value in an endless list, but unlike some other examples you have mentioned, it does not make any progress. It does not approximate a goal. It has nothing to output until it is done, which it never will be. Counting occurrences in some prefix was not the question.
The occurrences of an item in an infinite list fundamentally cannot be counted, except by a supertask, which is an interesting concept but not allowed in any reasonable model of computation.
Speaking about doing it in O(log n) as OP does is even more pointless, there isn't even an input size to set n to. There is no question about whether that's possible or not, the entire question cannot be asked.
|
|
|
|
|
Totally agree with you on the O (Log n) without more detail, I said that from outset.
I still am intrigued by your first part so let me throw you two very famous algorithms.
Quadratic sieve - Wikipedia[^]
General number field sieve - Wikipedia[^]
Both run forever and we rate them in MIPS-years because we expect them to never end.
In fact I know several maths departments have had them running for years with prime
numbers slowly being added to a file list as it finds them.
This one has been going 9 years, and hasn't output a number in over a year and it may
never put out another number ( Only the PRIME GODS know).
Great Internet Mersenne Prime Search - PrimeNet[^]
You will note the weird today stats on right hand side to even know it is still running
and you may get a laugh from the youtube video about the notification failing and the
discovery date being 3 months late.
Wikipedia and everyone I know calls them an algorithm .. except they fail your definition
they be finite and terminate
A prime number search meets the EXACT OP QUESTION, it is an infinite search and sieving is O(Log n)
Prime Factorization using Sieve O(log n) for multiple queries - GeeksforGeeks[^]
Sieve theory - Wikipedia[^]
My problem is you can't guarantee you can do it without knowing the data behaviour and if I can sieve it.
You claim such a thing can't be done and we shouldn't talk about it ... yet it exists .
I keep answering because you keep making out some sort of authoritative answer, you insist on
some definition but you never say by who, what authority?. I have shown you a number of
computer programming fields who don't agree with that definition and things you say are
impossible exist, so I am never going to agree with you. You are wasting time trying to argue
authority in such a situation. I don't doubt your definition may be true in your field and you
really truely believe it, but that doesn't work universally.
In vino veritas
modified 30-Oct-17 1:10am.
|
|
|
|
|
No you're just confusing GIMPS with the algorithms they use. Primality testing can trivially be done in finite time even with trial division. The Lucas-Lehmer test that GIMPS spends most its time doing also runs in finite time. Even factoring can be done in finite time with trial division. QS and GNFS do not need infinite sieving, they need an amount of sieving that depends on the smoothness bound B, which (while typically analyzed heuristically) is definitely finite (for example, it doesn't need to be any higher than the number being factored - that's a terrible bound but it makes B definitely finite). GIMPS as a whole doesn't have an end in sight because they can just keep looking for more Mersenne primes, but it's a project, not an algorithm.
You have not shown that anything that I have said does not exist actually does, you have called various things infinite that aren't, and named an example of an infinite process that isn't an algorithm. The one thing you could have mentioned that is slightly troubling in the face of the finiteness of algorithms is the class of Las Vegas algorithms, which seems to defy the definition. But they terminate in finite time with probability 1.
As for the definition, it's on wikipedia among other places. See also effective method. Not authoritative enough? Check the sources.
|
|
|
|
|
Interesting I need to give that some more thought to see if it works for me.
Most of us mathematicians and programmers are obviously just lazy and call it the Mersenne Primes algorithm,
we know there are a couple of small sub section algorithms running under it. I can honestly say I have never
thought much about it until this question.
The problem I have is if I take it out to computability like you have (and your link), Mersenne Primes is not
an Algorithm, it's not an Effective method (it doesn't terminate) .. it's not anything and you ended up calling
it a project .. which I now understand. A project to me is meaningless and while to you it's just a formal
definition, I lose working meaning and I am not sure I want to go that far just to get a definition
What is common to all the group of things that are causing problems is they all expel intermediate results
and it is the intermediate results that are more important than the "project" terminating (using your terms).
I see where you are going but I need time to think about it because this is tricky with this class of problems,
I am even needing to look carefully at the definition of computability. A couple of the fractal situations are
probably classed as not computabile.
In vino veritas
modified 30-Oct-17 10:37am.
|
|
|
|
|
Quote: how is that possibble, i mean you must go through all the elements..
It is not possible, actually.
Yes, you have to go through all the elements.
|
|
|
|
|
alogaritm for mini calender project
|
|
|
|
|
|
hello
this is a try at a verry simple game
it is a try at moving a circle whit cursor-key's
i use code::block's
4 error's were detected :
somting wrong whit case
any help is welkome
#if defined(UNICODE) && !defined(_UNICODE)
#define _UNICODE
#elif defined(_UNICODE) && !defined(UNICODE)
#define UNICODE
#endif
#include <tchar.h>
#include <windows.h>
bool key[ 256 ] ;
int playerx , playery , winx , winy ;
#define FRAME_TIMER 1
LRESULT CALLBACK WindowProcedure (HWND, UINT, WPARAM, LPARAM);
TCHAR szClassName[ ] = _T("CodeBlocksWindowsApp");
int WINAPI WinMain (HINSTANCE hThisInstance,
HINSTANCE hPrevInstance,
LPSTR lpszArgument,
int nCmdShow)
{
HWND hwnd;
MSG messages;
WNDCLASSEX wincl;
wincl.hInstance = hThisInstance;
wincl.lpszClassName = szClassName;
wincl.lpfnWndProc = WindowProcedure;
wincl.style = CS_DBLCLKS;
wincl.cbSize = sizeof (WNDCLASSEX);
wincl.hIcon = LoadIcon (NULL, IDI_APPLICATION);
wincl.hIconSm = LoadIcon (NULL, IDI_APPLICATION);
wincl.hCursor = LoadCursor (NULL, IDC_ARROW);
wincl.lpszMenuName = NULL;
wincl.cbClsExtra = 0;
wincl.cbWndExtra = 0;
wincl.hbrBackground = (HBRUSH) COLOR_BACKGROUND;
if (!RegisterClassEx (&wincl))
return 0;
hwnd = CreateWindowEx (
0,
szClassName,
_T("Game 1"),
WS_OVERLAPPEDWINDOW | WS_MAXIMIZE ,
CW_USEDEFAULT,
CW_USEDEFAULT,
800,
600,
HWND_DESKTOP,
NULL,
hThisInstance,
NULL
);
ShowWindow (hwnd, nCmdShow);
while (GetMessage (&messages, NULL, 0, 0))
{
TranslateMessage(&messages);
DispatchMessage(&messages);
}
return messages.wParam;
}
LRESULT CALLBACK WindowProcedure (HWND hwnd,
UINT message, WPARAM wParam, LPARAM lParam)
{
switch (message)
{
case WM_CREATE :
playerx = 100 ;
playery = 100 ;
SetTimer( hwnd
, FRAME_TIMER
, 40 , NULL ) ;
break ;
case WM_KEYDOWN :
key[ wParam ] = true ;
switch( wParam )
{
case VK_ESCAPE :
PostQuitMessage( 0 ) ;
break ;
default : ;
}
break ;
case WM_KEYUP :
key[ wParam ] = false ;
break ;
case WM_TIMER :
switch( wParam )
{
case FRAME_TIMER :
if ( key[ VK_UP ] ) playery-- ;
if ( key[ VK_DOWN ] ) playery++ ;
if ( key[ VK_LEFT ] ) playerx-- ;
if ( key[ VK_RIGHT ] ) playerx++ ;
if ( playery > winy ) playery = 0 ;
if ( playery < 0 ) playery = winy ;
if ( playerx > winx ) playerx = 0 ;
if ( playerx < 0 ) playerx = winx ;
InvalidateRect( hwnd , NULL , true ) ;
break ;
default : ;
}
break ;
case WM_PAINT :
PAINTSTRUCT paint ;
HDC hdc = BeginPaint( hwnd , &paint ) ;
RECT rect ;
GetClientRect( hwnd , &rect ) ;
winx = rect.right ;
winy = rect.bottom ;
Ellipse( hdc ,
playerx - 20 ,
playery - 20 ,
playerx + 20 ,
playery + 20 ) ;
EndPaint( hwnd , &paint ) ;
break ;
case WM_DESTROY :
PostQuitMessage( 0 ) ;
break ;
default :
return DefWindowProc (hwnd, message, wParam, lParam);
}
return 0 ;
}
|
|
|
|
|
You should at least report the exact error messages and mark the offending lines.
|
|
|
|
|
Most compilers object if you put local variables inside a case statement. You should either declare them before the first switch or enclose the case block in braces, thus:
case WM_PAINT :
{
PAINTSTRUCT paint ;
HDC hdc = BeginPaint( hwnd , &paint ) ;
RECT rect ;
GetClientRect( hwnd , &rect ) ;
winx = rect.right ;
winy = rect.bottom ;
Ellipse( hdc ,
playerx - 20 ,
playery - 20 ,
playerx + 20 ,
playery + 20 ) ;
EndPaint( hwnd , &paint ) ;
}
break ;
Also, in future, please provide the exact text of error messages, and indicate where they occur.
|
|
|
|
|
i tryed it [ thanks for sugestions
and
i got somthing on screen
error :
my screen isn't black and isn't fulscreen
my ellipse isn't yellow
#if defined(UNICODE) && !defined(_UNICODE)
#define _UNICODE
#elif defined(_UNICODE) && !defined(UNICODE)
#define UNICODE
#endif
#include <tchar.h>
#include <windows.h>
bool key[ 256 ] ;
int playerx , playery , winx , winy ;
#define FRAME_TIMER 1
LRESULT CALLBACK WindowProcedure (HWND, UINT, WPARAM, LPARAM);
TCHAR szClassName[ ] = _T("CodeBlocksWindowsApp");
int WINAPI WinMain (HINSTANCE hThisInstance,
HINSTANCE hPrevInstance,
LPSTR lpszArgument,
int nCmdShow)
{
HWND hwnd;
MSG messages;
WNDCLASSEX wincl;
wincl.hInstance = hThisInstance;
wincl.lpszClassName = szClassName;
wincl.lpfnWndProc = WindowProcedure;
wincl.style = CS_DBLCLKS;
wincl.cbSize = sizeof (WNDCLASSEX);
wincl.hIcon = LoadIcon (NULL, IDI_APPLICATION);
wincl.hIconSm = LoadIcon (NULL, IDI_APPLICATION);
wincl.hCursor = LoadCursor (NULL, IDC_ARROW);
wincl.lpszMenuName = NULL;
wincl.cbClsExtra = 0;
wincl.cbWndExtra = 0;
wincl.hbrBackground = (HBRUSH)BLACK_BRUSH;
if (!RegisterClassEx (&wincl))
return 0;
hwnd = CreateWindowEx (
0,
szClassName,
_T("Game 1"),
WS_OVERLAPPEDWINDOW | WS_MAXIMIZE ,
CW_USEDEFAULT,
CW_USEDEFAULT,
800,
600,
HWND_DESKTOP,
NULL,
hThisInstance,
NULL
);
ShowWindow (hwnd, nCmdShow);
while (GetMessage (&messages, NULL, 0, 0))
{
TranslateMessage(&messages);
DispatchMessage(&messages);
}
return messages.wParam;
}
LRESULT CALLBACK WindowProcedure (HWND hwnd,
UINT message, WPARAM wParam, LPARAM lParam)
{
PAINTSTRUCT paint ;
HDC hdc = BeginPaint( hwnd , &paint ) ;
RECT rect ;
HBRUSH brush =
CreateSolidBrush( RGB(255,255,0) ) ;
HPEN pen =
CreatePen( PS_SOLID ,
0 ,
RGB(255,255,0) ) ;
switch (message)
{
case WM_CREATE :
playerx = 100 ;
playery = 100 ;
SetTimer( hwnd
, FRAME_TIMER
, 40 , NULL ) ;
break ;
case WM_KEYDOWN :
key[ wParam ] = true ;
switch( wParam )
{
case VK_ESCAPE :
PostQuitMessage( 0 ) ;
break ;
default : ;
}
break ;
case WM_KEYUP :
key[ wParam ] = false ;
break ;
case WM_TIMER :
switch( wParam )
{
case FRAME_TIMER :
if ( key[ VK_UP ] ) playery-- ;
if ( key[ VK_DOWN ] ) playery++ ;
if ( key[ VK_LEFT ] ) playerx-- ;
if ( key[ VK_RIGHT ] ) playerx++ ;
if ( playery > winy ) playery = 0 ;
if ( playery < 0 ) playery = winy ;
if ( playerx > winx ) playerx = 0 ;
if ( playerx < 0 ) playerx = winx ;
InvalidateRect( hwnd , NULL , true ) ;
break ;
default : ;
}
break ;
case WM_PAINT :
GetClientRect( hwnd , &rect ) ;
winx = rect.right ;
winy = rect.bottom ;
Ellipse( hdc ,
playerx - 20 ,
playery - 20 ,
playerx + 20 ,
playery + 20 ) ;
EndPaint( hwnd , &paint ) ;
break ;
case WM_DESTROY :
PostQuitMessage( 0 ) ;
break ;
default :
return DefWindowProc (hwnd, message, wParam, lParam);
}
return 0 ;
}
|
|
|
|
|
You are calling BeginPaint for every message (not just WM_PAINT), but you only call EndPaint after processing a WM_PAINT message. You need to move all code related the the painting into the block that handles the WM_PAINT message. You also need to select your brushes and pens into the device context before you draw anything. And lastly you need to delete any DC objects that you use in painting.
I would suggest studying the GDI documentation on MSDN for sample code. But be aware that GDI and GDI+ are being deprecated by Microsoft in favour of Direct2D API Reference (Windows)[^]
|
|
|
|
|
Hi all of you. I come here hoping to solve a problem that I have met on retrieving data from DB (SQL Server).
I retrieve data in the following way:
pRs->GetFieldValue(i, *pDBVariant);
nothing special ... (pRS is CRecordset*, and pDBVariant is CDBVariant*).
And this is method to format data:
CString CMyDoc::FormatData(CDBVariant* pDBVariant)
{
CString sRet;
do
{
if(NULL == pDBVariant)
break;
switch(pDBVariant->m_dwType)
{
case DBVT_LONG:
TRACE("DBVT_LONG\n");
sRet.Format(_T("%d"), pDBVariant->m_lVal);
break;
case DBVT_DOUBLE:
TRACE("DBVT_DOUBLE\n");
break;
case DBVT_SHORT:
TRACE("DBVT_SHORT\n");
break;
case DBVT_SINGLE:
TRACE("DBVT_SINGLE\n");
break;
case DBVT_STRING:
TRACE("DBVT_STRING\n");
break;
case DBVT_ASTRING:
TRACE("DBVT_ASTRING\n");
sRet = *pDBVariant->m_pstring;
break;
case DBVT_DATE:
TRACE("DBVT_DATE\n");
break;
case DBVT_WSTRING:
TRACE("DBVT_WSTRING\n");
CStringW wstring = *pDBVariant->m_pstringW;
sRet = CString(wstring);
break;
}
}
while(FALSE);
return sRet;
}
I have the following SQL:
SELECT nUser FROM my_table;
nUser has int SQL data type, and when I test this data with CMyDoc::FormatData, the returning data type are: DBVT_LONG
Ok, let take another SQL:
SELECT dVAT FROM my_table;
dVAT has decimal (10.2) SQL data type, and when I test this data with CMyDoc::FormatData, the returning data type are: DBVT_ASTRING ... why ?
I have tested another SQL:
SELECT sName FROM my_table;
sName has string SQL data type, and when I test this data with CMyDoc::FormatData, the returning data type are: DBVT_ASTRING, which are ok ...
but, excepting int SQL data type, all other SQL data type are having DBVT_ASTRING when I test this with CMyDoc::FormatData ... why ?
Can you help me ?
Thank you.
|
|
|
|
|
Have you checked the actual data returned in the variant to see whether it is a string or the value type you expect?
|
|
|
|
|
I re-written the FormatData method:
CString CMyDoc::FormatData(CDBVariant* pDBVariant)
{
CString sRet;
switch(pDBVariant->m_dwType)
{
case DBVT_LONG:
TRACE("DBVT_LONG\n");
sRet.Format(_T("%d"), pDBVariant->m_lVal);
break;
case DBVT_DOUBLE:
TRACE("DBVT_DOUBLE\n");
break;
case DBVT_SHORT:
TRACE("DBVT_SHORT\n");
break;
case DBVT_SINGLE:
TRACE("DBVT_SINGLE\n");
break;
case DBVT_STRING:
TRACE("DBVT_STRING\n");
break;
case DBVT_ASTRING:
TRACE("DBVT_ASTRING\n");
sRet = *pDBVariant->m_pstring;
break;
case DBVT_DATE:
TRACE("DBVT_DATE\n");
break;
case DBVT_WSTRING:
TRACE("DBVT_WSTRING\n");
CStringW wstring = *pDBVariant->m_pstringW;
sRet = CString(wstring);
break;
}
return sRet;
}
I have the following SQL:
SELECT nUser FROM my_table
In DB, nUser has "int" type. The result in FormatData method: DBVT_LONG
I have another SQL:
SELECT dValue FROM my_table
In DB, dValue has "decimal (10.2)" type. The result in FormatData method: DBVT_ASTRING !? Why ?
I have another SQL:
SELECT sName FROM my_table
In DB, dValue has "varchar(1024)" type. The result in FormatData method: DBVT_ASTRING - correct.
I noticed that any king of column type in DB, except "int" type, return DBVT_ASTRING in FormatData method ... why ?
I have tried to get data with CRecordset as dynaset, snaphot and dynamic ... every one of them had the same result ...
|
|
|
|
|
That is what you wrote in your original question, and removing the unnecessary do ... while() is not going to affect things. The issue is, what value type is SQL returning into your recordset? What you are looking at here is happening long after the data has been sent from the database.
|
|
|
|
|
What you have described sounds perfectly correct depending how you set the tables up.
Your nUser will be (look at SQL spec integer value between the range 2^ -31 and 2^31 -1) which is 32 bits or 4 bytes and would be a long in C/C++.
Your decimal (10.2) will be stored as an IEEE-754/-854-compliant bit string which will be 5-17 bytes.
If you stored your decimal(10.2) as singles/doubles you would get issues when you added them etc the small fractions you can't see would roll do you understand lets add 3 digits with 3 decimal places
Stored .... 10.2 format
-------------------------
1.344 .... 1.34
2.364 .... 2.36
1.134 .... 1.13
----------------------
4.842 .... 4.83
See the Problem 4.842 down to 2 digits is 4.84 and is not right answer they don't give same result and that is why SQL does not automatically covert numbers with precision.
I am sure if you make a table of doubles, single or floats they will come back as that just don't expect that from decimal, numeric which will be strings
In vino veritas
modified 25-Oct-17 15:22pm.
|
|
|
|
|
Yes, you are right ... I must change the data type in SQL in order to get right values in CDBVariant ... but I should ask this to my SQL colleagues ... 
Kindly thank you for your answer !!
|
|
|
|
|
It's unrelated to the problem but why the unnecessary do/while loop?
"One man's wage rise is another man's price increase." - Harold Wilson
"Fireproof doesn't mean the fire will never come. It means when the fire comes that you will be able to withstand it." - Michael Simmons
"You can easily judge the character of a man by how he treats those who can do nothing for him." - James D. Miles
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
