C++

Forum

 
How to count lines of cout?

Pages: 123
jonnin (11380)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
 
//#include "stdafx.h"
#include <cstdlib>
#include <vector>
#include <iostream>
#include <iterator>
#include <ctime> //C++ version!
#include <fstream>
#include <cstdio>

using namespace std;
static double counter = 0;

void print_partitions(unsigned long long sum_val, unsigned long long n) {
	unsigned long long pos = 0, last = n - 1;
	vector<unsigned long long> a(n);//unsigned long long a[n] dosent work
	for (unsigned long long i = 1; i != n; ++i)
		a[i] = 0;
	a[0] = sum_val;
	while (true) {
		//for (unsigned long long i = 0; i != last; ++i)
		//	printf("%3d ", a[i]);
		//	printf("%3d\n", a[last]);
		   ++counter;
		if (pos != last) {
			--a[pos];
			++pos;
			a[pos] = 1;
		}
		else {
			if (a[last] == sum_val)
				return;
			for (--pos; a[pos] == 0; --pos);
			--a[pos];
			unsigned long long tmp = 1 + a[last];
			++pos;
			a[last] = 0;
			a[pos] = tmp;
		}
	}
}
int main() {
	system("color F1");
	char yn;
	do {
		counter = 0;
		cout << "input v:  ";
		unsigned long long v,z,z1;
		cin >> v;
		z = v + 1;
		z1 = v;
		const clock_t begin_time = clock();
		for (v = 1; v < z; v++) {
			print_partitions(v, z1);
		}
		cout<<" :  "<<counter+1<<endl;
		cout <<  " :  " << float(clock() - begin_time) / CLOCKS_PER_SEC << endl;
		cout << "y\n";
	} while (cin >> yn && (yn == 'Y' || yn == 'y'));
	return 0;
}
jonnin (11380)
this is kind of interesting... its slightly off, but is it good enough? edit, I think its exact now. 
1
2
3
4
5
6
7
 
//for (v = 1; v < z; v++) 
		{
			print_partitions(z-1, z1);
		//	print_partitions(v, z1);
		}
		cout<<" :  "<<2*(counter)<<endl; 
		//cout<<" :  "<<counter+1<<endl;


also, a slight tweak:
static vector<unsigned long long> a(n);//unsigned long long a[n] dosent work

this is also interesting. Its an approximation. It runs in about 1 nanosecond. Its not quite right, but I am thinking if someone put some energy into it, you could find a direct computation of your answer. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
 
int main()
{
  unsigned long long  t=2;
  for(unsigned long long i = 1; i < 25; i++)
  {
	t = t* min((3.0+ 0.166666666*i), 3.8);
    cout << t << endl;
	
  }

output of approximate vs actual:

C:\c>a
C:\c>a
1 6 6
2 19 20
3 66 70
4 241 252
5 915 924
6 3476 3432
7 13208 12870
8 50190 48620
9 190721 184756
10 724739 705432
11 2754008 2704156
12 10465230 10400600
13 39767873 40116600
14 151117917 155117520
15 574248084 601080390
16 2182142719 2333606220

and just the approximation out to 30: (warning, by here it has hit the 3.8 min in the 
equation and it may not be correct this far out).  
20 483427915062
21 1837026077235
22 6980699093492
23 26526656555269
24 100801294910022
25 383044920658083
26 1455570698500715
27 5531168654302716
28 21018440886350319
29 79870075368131212
Last edited on
jonnin (11380)
from the real answers ... the ratio ... so it slowly grows past 3.8. Looking for a pattern .. if you can nail this sequence ...

3
3.33333
3.5
3.6
3.66667
3.71429
3.75
3.77778
3.8
3.81818
3.83333
3.84615
3.85714
3.86667
3.875
Last edited on
jonnin (11380)
got it... working... looks like 3.0 + 1/3, 1/6 (+3), 1/10 (+4), 1/15 (+5) ...

much closer, but still not exact.

int main()
{
unsigned long long t=2;
//unsigned long long p=2;
double pd = 0;
int den = 3;
for(unsigned long long i = 3; i < 25; i++)
{
pd += 1.0/den;
den += i;
t *= (3.0+pd);
if( i == 17) t = 601080390; //catchup/manual correction (yea, i cheated!)
cout << t << endl;
}
}

That is about the best I could do with it. If you look at your function's answers divided by the previous one, you get the 3,3.33, etc sequence. Looking at the difference between those, its 3.0 + a running sum (1/3 + 1/6 + 1/10 etc). The code is doing THAT but its still not exact, either floating point errors or these ratios are close but not exact or something of that nature. Anyone see anything I did wrong or have a better way to compute it??
Last edited on
Alex009988 (34)
Thank you for your reply.
Do you remember I was telling about that there is two anomal points.
So take a look
2., 3., 3.33333, 3.5, 3.6, 3.66667, 3.71429, 3.75, 3.77778, 3.8, \
3.81818, 3.83333, 3.84615, 3.85714, 2.86957, 5.22145, 3.88235, \
3.88889, 3.89474, 3.9, 3.90476
That's why my mathematica cant find a formula because of these two points.
Unfortunately, these two numbers spoil all the picture. Perhaps, there is some further anomal points far away.
Last edited on
jonnin (11380)
I remember now :( My list did not generate those 2 values. Are you sure about them?! I got 3.85714
3.86667
3.875
I also swapped to u64 bit ints. Maybe something happened size-wise?

Well, at least the loop-skip tweak should shave off some major time. Do you agree with it? It seems to be exact?

its also really about how much of an approximation you can tolerate.
Last edited on
lastchance (6980)
What on earth are you doing?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
#include <iostream>
#include <vector>
using namespace std;

int main()
{
   int v = 32;
   vector<unsigned long long> S( v + 2, 0 );
   for ( int j = 1; j <= v + 1; j++ )
   {
      S[0] = 1;
      for ( int i = 1; i <= v; i++ )
      {
         S[i] += S[i-1];
         if ( i == j - 1 ) cout << "v" << i << " = " << S[i] << '\n';
      }
   }
}



v1 = 2
v2 = 6
v3 = 20
v4 = 70
v5 = 252
v6 = 924
v7 = 3432
v8 = 12870
v9 = 48620
v10 = 184756
v11 = 705432
v12 = 2704156
v13 = 10400600
v14 = 40116600
v15 = 155117520
v16 = 601080390
v17 = 2333606220
v18 = 9075135300
v19 = 35345263800
v20 = 137846528820
v21 = 538257874440
v22 = 2104098963720
v23 = 8233430727600
v24 = 32247603683100
v25 = 126410606437752
v26 = 495918532948104
v27 = 1946939425648112
v28 = 7648690600760440
v29 = 30067266499541040
v30 = 118264581564861424
v31 = 465428353255261088
v32 = 1832624140942590534
Alex009988 (34)
Year, I'm 100500% sure. Just take a look at the ratio of v16/15, v15/14.
lastchance (6980)
Alex009988, did you see my post?
jonnin (11380)
Did I mess something up? I just did this with my above code to get the ratios..

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
 
unsigned long long int xmain(int in) {
	//system("color F1");
	char yn;
	//do {
		counter = 0;
		//cout << "input v:  ";
		unsigned long long v,z,z1;
		//cin >> v;
		v = in;
		z = v + 1;
		z1 = v;
		const clock_t begin_time = clock();
		//for (v = 1; v < z; v++) 
		{
			print_partitions(z-1, z1);
		//	print_partitions(v, z1);
		}
		return 2*counter;
		cout<<" :  "<<2*(counter)<<endl;
		//cout<<" :  "<<counter+1<<endl;
		cout <<  " :  " << float(clock() - begin_time) / CLOCKS_PER_SEC << endl;
		cout << "y\n";
	//} //while (cin >> yn && (yn == 'Y' || yn == 'y'));
	return 0;
}

int main()
{
	 unsigned long long  t=2;
     unsigned long long  p=2;
	 double d;
	for(unsigned long long i = 1; i < 18; i++)
  {	 
     t = xmain(i);
	 d = (double)t/p;
	 p = t;
	 cout << d << endl;
	
  }

3
3.33333
3.5
3.6
3.66667
3.71429
3.75
3.77778
3.8
3.81818
3.83333
3.84615
3.85714
3.86667
3.875
3.88235


lastchance (6980)
@jonnin, why are you banging on about this? It takes less than a second to compute v32.
http://www.cplusplus.com/forum/beginner/249168/2/#msg1099269
Last edited on
Alex009988 (34)
601080390/155117520= 5.22
Oh my God. @lastchance. I dont believe my eyes. How is this possible.
I dont fully understand how it gets the result so quickly.
Would you mind to give some comments? Thanks in advance.
I see it uses some array operations without the matrix generated.
jonnin (11380)
your post hadn't come through yet, had to refresh.
v15/14 from lastchance's list is 3.8x ... there isnt any anomaly, not that it matters if theres a quick algorithm for it.
Last edited on
Alex009988 (34)
Wait v15/14 is 115117520/40116600 is 2.869. Am I right?
jonnin (11380)
you are correct. but from lastchance's values, 14 and 15 are.. they are not the same values. And I got the same as he did. ... where did 11511 come from, vs 15511.
40116600
v15 = 155117520 this is why you see an anomaly, your #15 is wrong so 14/15 and 15/16 had a malfunction.

There isnt much point now, but I am firmly convinced there is a sequence behind this thing that would get it equally as fast as LC's code, though dealing with roundoff errors is going to make it an approximation vs his very clean exact answer. I got 27 = 2265962932982288 vs 1946939425648112 (194 vs 226, not great, but ballpark -- 15% error is starting to get too much). I am probably going to try to drive the error down if I can, just for fun at this point.
Last edited on
lastchance (6980)
Alex009988 wrote:
I dont fully understand how it gets the result so quickly.
Would you mind to give some comments?


Inductive derivation here:
https://imgur.com/a/rGsk9do


Slightly simplified version of the code below. It will overflow unsigned long long shortly above v = 32.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
#include <iostream>
#include <vector>
using namespace std;

int main()
{
   int v = 32;
   vector<unsigned long long> S( v + 1, 0 );
   for ( int j = 1; j <= v + 1; j++ )
   {
      S[0] = 1;
      for ( int i = 1; i <= v; i++ ) S[i] += S[i-1];
      if ( j > 1 ) cout << "v" << j - 1 << " = " << S[j-1] << '\n';
   }
}


v1 = 2
v2 = 6
v3 = 20
v4 = 70
v5 = 252
v6 = 924
v7 = 3432
v8 = 12870
v9 = 48620
v10 = 184756
v11 = 705432
v12 = 2704156
v13 = 10400600
v14 = 40116600
v15 = 155117520
v16 = 601080390
v17 = 2333606220
v18 = 9075135300
v19 = 35345263800
v20 = 137846528820
v21 = 538257874440
v22 = 2104098963720
v23 = 8233430727600
v24 = 32247603683100
v25 = 126410606437752
v26 = 495918532948104
v27 = 1946939425648112
v28 = 7648690600760440
v29 = 30067266499541040
v30 = 118264581564861424
v31 = 465428353255261088
v32 = 1832624140942590534
Last edited on
jonnin (11380)
Well its no news to anyone here but I am an idiot, I was off by one in the sequence lol. It still has roundoff but its tiny and about what we expect now that the multiplier is in sync with the running value instead of shifted :)

so here it is as a sequence, single loop and Im done with it. (I got this yesterday, just now getting back to posting it though). And yes, I know, but it was bugging me that it wasn't right before. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 
unsigned long long  t=6;  
  long double  pd = 0;
  int den = 3;
  for(unsigned long long i = 3; i < 40; i++)
  {	 
	pd +=  1.0/den;	
	den += i;	
	t *= (3.0+pd); 	
	cout <<  t<< endl;
  }

2 20   //my counter is just a counter, not related to sequence position
3 70
4 252
5 924
6 3432
7 12870
8 48620
9 184756
10 705432
11 2704156
12 10400600
13 40116600
14 155117520
15 601080390
16 2333606220
17 9075135300
18 35345263800
19 137846528820
20 538257874439
21 2104098963716
22 8233430727584
23 32247603683037
24 126410606437505
25 495918532947134
26 1946939425644303
27 7648690600745476
28 30067266499482216
29 118264581564630049
30 465428353254350515
31 1832624140939005152



Last edited on
Grime (651)
lastchance which tool did you use for that picture?

I feel like I've asked you this before but if I have then I've probably forgotten..
Also I envy your math skillz.
Last edited on
lastchance (6980)
Grime wrote:
lastchance which tool did you use for that picture?


It's just word-processed in Microsoft Word, saved as a PDF, re-opened in the GIMP, cropped to size, exported as a PNG file. Nothing's straightforward in this world!

Took a lot longer than my scribbled original version on the back of my telephone bill, which I actually used to code from.
Last edited on
Enoizat (1342)
Microsoft Word ... PDF ... GIMP ... cropped ... PNG

LibreOffice provides an “export as png” option, and you can choose the final dimensions in the simple exporting mask (with the utmost respect for Ms Word, of course).
Pages: 123